23 Merge k Sorted Lists

1. Question

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

2. Implementation

(1) Divide and Conquer
1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode mergeKLists(ListNode[] lists) {
11
return mergeKLists(lists, 0, lists.length - 1);
12
}
13
14
public ListNode mergeKLists(ListNode[] lists, int start, int end) {
15
if (start > end) {
16
return null;
17
}
18
19
if (start == end) {
20
return lists[start];
21
}
22
23
int mid = start + (end - start) / 2;
24
ListNode left = mergeKLists(lists, start, mid);
25
ListNode right = mergeKLists(lists, mid + 1, end);
26
return mergeTwoLists(left, right);
27
}
28
29
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
30
ListNode dummy = new ListNode(0);
31
ListNode curNode = dummy;
32
ListNode p1 = l1, p2 = l2;
33
34
while (p1 != null && p2 != null) {
35
if (p1.val < p2.val) {
36
curNode.next = p1;
37
p1 = p1.next;
38
}
39
else {
40
curNode.next = p2;
41
p2 = p2.next;
42
}
43
curNode = curNode.next;
44
}
45
46
if (p1 != null) {
47
curNode.next = p1;
48
}
49
else {
50
curNode.next = p2;
51
}
52
return dummy.next;
53
}
54
}
Copied!
(2) Heap
1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode mergeKLists(ListNode[] lists) {
11
if (lists == null || lists.length == 0) {
12
return null;
13
}
14
15
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
16
@Override
17
public int compare(ListNode l1, ListNode l2) {
18
return l1.val - l2.val;
19
}
20
});
21
22
for (ListNode head : lists) {
23
if (head != null) {
24
minHeap.add(head);
25
}
26
}
27
28
ListNode dummy = new ListNode(0);
29
ListNode curNode = dummy;
30
31
while (!minHeap.isEmpty()) {
32
curNode.next = minHeap.remove();
33
curNode = curNode.next;
34
35
if (curNode.next != null) {
36
minHeap.add(curNode.next);
37
}
38
}
39
return dummy.next;
40
}
41
}
Copied!

3. Time & Space Complexity

Divide and Conquer: 时间复杂度O(nlogk), k是lists的个数, n是merge两个list时,两个list的node总个数,空间复杂度O(1)
Heap: 时间复杂度O(nlogk), k是lists的个数, n是所有list的node的总数,空间复杂度O(k)