GuilinDev
Lc0021
05 August 2008
21 Merge Two Sorted Lists
原题概述
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.
Example:
1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
题意和分析
这道题很可能跟Merge Sorted Array一起问。可以用递归方法，判断哪个链表的节点值小就把该节点的下一个节点递归，最后返回最小的那个head；迭代，比较直接，两个链表都不为空的时候按顺序比较就是。
两个方法相同，Time：O(m+n)；Space，因为每次递归辅助空间是线性的而不是二分减少，所以应该O(m + n)。
利用虚拟节点（dummy node），虚拟节点是当我们合并两个链表时不知道哪个节点是新链表节点的头节点时会用到。对于我们之前提到的这个问题，我们会用到两个指针p1（指向L1头节点）、p2（指向L2头节点），前面提到的虚拟节点和当前节点（current node，用于循环，被初始化指向虚拟节点）。通过循环访问所有节点来构成新的链表。在每次循环中，会比较两个链表中p1和p2指向的节点的值，使当前节点一直指向较小值节点的下一节点。如下图：
在第一步中，p1指向的节点值为2，p2指向节点值为6,2小于6，所以curr指向p1，p1指向下一节点，即指向节点值为5的节。
第二步中，p1指向的节点的值仍然小于p2指向的节点的值，所以继续向后移动。
第三步中，p1指向的节点的值大于p2指向的节点的值，curr指向p2当前指向的节点，p2向后移动。
以此类推，直到p1或者p2指针移动到链表的末端，因为我们在每次比较中都选择较小的值，所以当p1或者p2中任何一个指针指向链表末端，代表另外一个没有还没到达末端的链表的后序的值都比已到达末端的链表中最大的值要大，所以只需要将后续的节点追加到新的链表后即可。
也可以用递归的方式解决这个问题。递归（recursion）是一种在计算机科学中非常基本且普遍的思考问题的方式。典型的递归思路就是可以把问题变为更小的问题，并且这个更小的问题可以继续递归成更小的问题，知道这个问题小到到达一个边界条件（boundary condition），以至于可以很轻松地解决。
在这个问题中，我们的边界条件很简单，就是当L2指向了null，返回L1或者L1指向了null，返回L2。如果L1或者L2没有指向null，就需要比较L1和L2对应的值哪个更小，当有结果以后，这个新的链表就更长了，而需要比较的链表就更短了，显然，这样这个问题就比较之前的简单了，如此反复递归即可。
代码
递归
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
/**
* 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) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;//l1是第一个node
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;//l2是第一个node
}
}
}
迭代
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
/**
* 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) {
if(l1 == null || l2 == null){
return l1 == null ? l2 : l1;
}
ListNode dummy = new ListNode(-1), current = dummy;//维持住头部好返回,-1和0都一样
while(l1 != null && l2 != null){
if(l1.val <=l2.val){
current.next = l1;
l1 = l1.next;
} else{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1==null ? l2 : l1; //如果一个链表已经迭代结束，那么就把另外一条链表剩余部分直接加入
return dummy.next;
}
}