首页 > 代码库 > No.021：Merge Two Sorted Lists

No.021：Merge Two Sorted Lists

2024-08-23 19:53:31   217人阅读

问题：

Merge two sorted linked lists and return it as a new list.

The new list should be made by splicing together the nodes of the first two lists.

 

官方难度：

Easy

 

翻译：

合并2个已排序的链表，得到一个新的链表并且返回其第一个节点。

 

  1. 考虑输入节点存在null的情况，直接返回另一个节点。
  2. 节点的定义在No.002（Add Two Numbers）中有定义。
  3. 记录上一个节点last，保留第一个节点first。
  4. 以其中一条链表为基准，作为待排序的链表，其第一个节点记为l1。比较l1和l2的value值，如果l1的value是较大的一方，交换l1和l2节点，保证last节点的next指针指向l1节点。
  5. 当l1节点的next指针为null时，表明第一条链表完全有序，且最后一个节点的值小于另一条链表第一个节点的值，连接这两个节点，整条链表自然有序。

 

解题代码：

技术分享 
 1     public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 2         if (l1 == null) {
 3             return l2;
 4         }
 5         if (l2 == null) {
 6             return l1;
 7         }
 8         // 返回的第一个节点
 9         ListNode first = l1.val > l2.val ? l2 : l1;
10         // 上一个节点
11         ListNode last = new ListNode(0);
12         while (true) {
13             if (l1.val > l2.val) {
14                 // 交换l1节点和l2节点，保证下一次循环仍然以l1节点为基准
15                 ListNode swapNode = l2;
16                 l2 = l1;
17                 l1 = swapNode;
18             }
19             // 将last节点的next指针指向l1，同时更新last
20             last.next = l1;
21             last = l1;
22             // 带排序的链表遍历完成，剩余链表自然有序
23             if (l1.next == null) {
24                 l1.next = l2;
25                 break;
26             }
27             l1 = l1.next;
28         }
29         return first;
30     }
mergeTwoLists

 

相关链接：

https://leetcode.com/problems/merge-two-sorted-lists/

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q021.java

 

PS：如有不正确或提高效率的方法，欢迎留言，谢谢！

 

No.021：Merge Two Sorted Lists


联系
我们