LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

题意

合并k个链表,每个链表内部都是排好序的(从小到大),但是k个链表之间是无序的。

思路

首先,最简单的办法就是链表之间选择排序,取第一个链表的第一个节点插到结果中。然后如果链表还有节点,放回到数组中。如此往复,直到没有节点剩余。

时间复杂度O(k*n),空间复杂度O(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
// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
ListNode head = null;
int hi = -1;
// 选出一个head
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && (head == null || lists[i].val < head.val)) {
head = lists[i];
hi = i;
}
}

if (head == null)
return head;
lists[hi] = lists[hi].next;
ListNode prev = head;

while (true) {
ListNode cur = null;
int ci = 0;
// 选出最小的node
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && (cur == null || lists[i].val < cur.val)) {
cur = lists[i];
ci = i;
}
}
if (cur == null)
break;
// 插入到链表中
lists[ci] = lists[ci].next;
prev.next = cur;
cur.next = null;
prev = cur;
}

return head;
}
}

显然,多次对k个链表排序是很浪费的,这时候就想到了堆,只需要将k个链表构成一个堆即可。时间复杂度O(N*log(k)),空间复杂度O(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
49
50
51
52
53
54
55
56
57
58
// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 43.2 MB
class Solution {
private int len;

public void adjust(ListNode[] lists, int startIndex) {
ListNode start = lists[startIndex];
int currIndex = startIndex;
while (currIndex < len) {
int nextIndex = currIndex * 2 + 1;
if (nextIndex + 1 < len && lists[nextIndex + 1].val < lists[nextIndex].val) {
nextIndex += 1;
}
if (nextIndex < len && start.val > lists[nextIndex].val) {
lists[currIndex] = lists[nextIndex];
currIndex = nextIndex;
} else {
break;
}
}
lists[currIndex] = start;
}

public ListNode mergeKLists(ListNode[] lists) {
len = lists.length;
// 剔除null
for (int i = 0; i < len; ) {
if (lists[i] == null) {
lists[i] = lists[--len];
} else {
i++;
}
}
ListNode head = null;
ListNode tail = null;
// i==0时的调整交给下面的while循环
for (int i = len / 2; i > 0; i--) {
adjust(lists, i);
}
while (len > 0) {
adjust(lists, 0);
if (tail == null) {
head = tail = lists[0];
} else {
tail.next = lists[0];
tail = tail.next;
}
if (tail.next != null) {
lists[0] = tail.next;
} else {
lists[0] = lists[len - 1];
len--;
}
tail.next = null;
}
return head;
}
}

接下来,看了官方的解法,发现还有一种 Merge with Divide And Conquer,如图:

和堆的解法一样,时间复杂度O(N*log(k)),空间复杂度O(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
// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 41.6 MB
class Solution {
private ListNode mergeTwoLists(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int med = (left + right) / 2;
ListNode l1 = mergeTwoLists(lists, left, med);
ListNode l2 = mergeTwoLists(lists, med + 1, right);

ListNode head = null;
ListNode tail = null;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
if (tail == null) {
head = tail = l1;
} else {
tail.next = l1;
tail = tail.next;
}
l1 = l1.next;
} else {
if (tail == null) {
head = tail = l2;
} else {
tail.next = l2;
tail = tail.next;
}
l2 = l2.next;
}
tail.next = null;
}
if (tail != null) {
tail.next = l1 != null ? l1 : l2;
} else {
head = l1 != null ? l1 : l2;
}
return head;
}

public ListNode mergeKLists(ListNode[] lists) {
if (lists.length < 1) {
return null;
}
return mergeTwoLists(lists, 0, lists.length - 1);
}
}

在做LeetCode 215. Kth Largest Element in an Array的时候,发现自己几乎忘记了堆排序,很惭愧。所以做这道题目复习下。

LeetCode 23. Merge k Sorted Lists

https://www.robberphex.com/merge-k-sorted-lists/

作者

Robert Lu

发布于

2019-07-27

许可协议

评论