bicycle_journey-wallpaper

前面,我们实现了链表的 环检测 操作,本篇来聊聊,如何合并两个有序链表。

有序链表合并

Leetcode 21. Merge Two Sorted Lists

示例

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

使用虚假的 Head 节点

定义一个临时虚假的 Head 节点,再创建一个指向 tail 的指针,以便于在尾部添加节点。

对 ListNode1 和 ListNode2 同时进行遍历,比较每次取出来的节点大小,并绑定到前面 tail 指针上去,直到最终所有的元素全部遍历完。

最后,返回 dummyNode.next ,即为新链表的 head 节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(0);
ListNode tail = dummyNode;

while(true){
if(l1 == null){
tail.next = l2;
break;
}

if(l2 == null){
tail.next = l1;
break;
}

ListNode next1 = l1;
ListNode next2 = l2;

if(next1.val <= next2.val){
tail.next = next1;
l1 = l1.next;
}else{
tail.next = next2;
l2 = l2.next;
}
tail = tail.next;
}
return dummyNode.next;
}
}

递归

使用递归的方式,代码比遍历看上去简洁很多,但是它所占用的栈空间会随着链表节点数量的增加而增加。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode result = null;

if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}

if(l1.val <= l2.val){
result = l1;
result.next = mergeTwoLists(l1.next, l2);
}else{
result = l2;
result.next = mergeTwoLists(l1, l2.next);
}
return result;
}
}

相关练习

参考资料