[LeetCode]Merge Two Sorted Lists 合并两个排好序的链表

链接https://leetcode.com/problems/merge-two-sorted-lists/#/description

难度:Easy

题目: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.

翻译:合并两个排好序的链列,并将其作为新链表返回。新链表应通过将前两个列表的节点拼接在一起。

思路一:新建一个头指针指向0的临时链表,比较l1和l2的当前值的大小,把临时链表的next节点指向较小的节点,l1或者l2的指针后移一位,依次往下,直到l1或者l2为空,则把临时链表的next节点指向最后那段非空的链表,返回临时链表的第二个节点(头一个节点为0)。

参考代码一(Java)

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newList = new ListNode(0);
ListNode nextList = newList;

while(l1 != null && l2 != null){
if(l1.val < l2.val){
nextList.next = l1;
l1 = l1.next;
}else{
nextList.next = l2;
l2 = l2.next;
}
nextList = nextList.next;
}

if(l1 != null){
nextList.next = l1;
}else{
nextList.next = l2;
}

return newList.next;

}
}

思路二:使用递归法。构造一个临时链表,当l1当前节点的值大于l2当前节点的值时,我们把l2这个较小的值赋给临时链表的下一个节点,并将l2的下一个节点的值和l1当前节点的值放到下一次做对比,依次递归下去。

参考代码二(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val > l2.val) {
ListNode tmp = l2;
tmp.next = mergeTwoLists(l1, l2.next);
return tmp;
} else {
ListNode tmp = l1;
tmp.next = mergeTwoLists(l1.next, l2);
return tmp;
}
}
}