21. 合并两个有序链表
题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
1
2
2
我的方案
注意点：题目要求是，有序输出。
Java源码
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode add = new ListNode(0);
ListNode end = add;
while (true) {
if (l1 == null) {
end.next = l2;
break;
}
if (l2 == null) {
end.next = l1;
break;
}
if(l1.val <= l2.val){
end.next = new ListNode(l1.val);
end = end.next;
l1 = l1.next;
}else{
end.next = new ListNode(l2.val);
end = end.next;
l2 = l2.next;
}
}
return add.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
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
Dart源码
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode addNode = ListNode(0);
ListNode end = addNode;
while (true) {
if (l1 == null) {
end.next = l2;
break;
}
if (l2 == null) {
end.next = l1;
break;
}
if (l1.val <= l2.val) {
end.next = ListNode(l1.val);
end = end.next;
l1 = l1.next;
} else {
end.next = ListNode(l2.val);
end = end.next;
l2 = l2.next;
}
}
return addNode.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
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
推荐方案
递归解决
Java源码
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;
}
else
{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Dart源码
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;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11