题目:
leetcode 21.Merge Two Sorted Lists(easy)
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:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
题目大意：
合并两个有序的链表，返回一个新链表是两个链表拼接成的有序链表。
解题思路：
这道题有两种解题思路，一种是迭代方法(iteratively),一种是递归方法(recursively)。
第一种方法就是逐个比较,新建一个新链表，比较两个有序链表节点大小，然后接到新链表后面；
第二种方法就是利用归并排序的思想，如将原问题转换成规模更小的同质的问题。1
2如 l1:1->2->5
l2:0->3->4
第一步 return l2,即0->后面有序的部分，
第二步return l1,即0->1->后面有序的部分，之后以此类推。可以借鉴这个图解 ,图示很清晰！
代码：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
41
42
43
44
45
46
47
48
49Java:
iteratively:
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
if(l1 == null)
return l2;
else if(l2 == null)
return l1;
else{
ListNode head = new ListNode(0);
ListNode temp = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
temp.next = l1;
l1 = l1.next;
}
else{
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if(l1 == null)
temp.next = l2;
if(l2 == null)
temp.next = l1;
return head.next;
}
}
recursively:
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
if(l1 == null){
return l2;
}else if(l2 == null){
return l1;
}
else{
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
Python:
