Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
O(nklogk) runtime, O(k) space – Heap
1
2
3
4
5
|
public class {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length < 1)
return null;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);
ListNode head = new ListNode(0);
ListNode current = head;
for (ListNode node : lists) {
if (node != null)
minHeap.add(node);
}
while (!minHeap.isEmpty()) {
current.next = minHeap.poll();;
current = current.next;
if (current.next != null)
minHeap.offer(current.next);
}
return head.next;
}
|
O(nklogk) runtime, O(1) space – Divide and conquer using two way merge
1
2
3
4
5
|
public class {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
|
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
|
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length < 1)
return null;
return partition(lists, 0, lists.length - 1);
}
private ListNode partition(ListNode[] lists, int start, int end) {
if (start == end)
return lists[start];
int mid = (start + end) >> 1;
ListNode left = partition(lists, start, mid);
ListNode right = partition(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
private 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;
}
}
|
近期评论