Algorithm
本周做的算法题是 21. Merge Two Sorted Lists。
问题描述
合并两个有序单链表。例子：
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
思路
- 直接借鉴归并排序算法，时间复杂度O(min(n,m))。
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
|
public ListNode (ListNode l1, ListNode l2) {
if (null == l1) {
return l2;
}
if (null == l2) {
return l1;
}
ListNode res = null;
ListNode newL = null;
while (l1 != null && l2 != null) {
int valInL1 = l1.val;
int valInL2 = l2.val;
if (valInL1 <= valInL2) {
if (newL == null) {
res = newL = l1;
} else {
newL.next = l1;
newL = l1;
}
l1 = l1.next;
} else {
if (newL == null) {
res = newL = l2;
} else {
newL.next = l2;
newL = l2;
}
l2 = l2.next;
}
}
if (l1 != null) {
newL.next = l1;
}
if (l2 != null) {
newL.next = l2;
}
return res;
}
|
- 上面的代码比较啰嗦，能否简化一点，我们可以借助哑节点，进行处理。
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
|
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (null == l1) {
return l2;
}
if (null == l2) {
return l1;
}
ListNode head = new ListNode(-1);
ListNode res = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
res.next = l1;
l1 = l1.next;
} else {
res.next = l2;
l2 = l2.next;
}
res = res.next;
}
if (l1 != null) {
res.next = l1;
}
if (l2 != null) {
res.next = l2;
}
return head.next;
}
|
近期评论