Question
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Explanation
见code。
LeetCode 23. Merge k Sorted Lists
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
// Solution 1: heap
// private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>(){
// public int compare(ListNode left, ListNode right){
// return left.val - right.val;
// }
// };
// public ListNode mergeKLists(ListNode[] lists) {
// if (lists == null || lists.length == 0 ) return null;
// Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.length, ListNodeComparator);
// for (int i=0; i<lists.length; i++) {
// if (lists[i] != null) {
// heap.add(lists.get(i));
// }
// }
// ListNode dummy = new ListNode(0);
// ListNode tail = dummy;
// while(!heap.isEmpty()) {
// ListNode head = heap.poll();
// tail.next = head;
// tail = head;
// if (head.next != null) {
// heap.add(head.next);
// }
// }
// return dummy.next;
// }
// Solution 2: merge two by two
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return partition(lists, 0, lists.length - 1);
}
public ListNode partition(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];
if (start < end) {
int middle = (start + end) / 2;
ListNode n1 = partition(lists, start, middle);
ListNode n2 = partition(lists, middle+1, end);
return merge(n1, n2);
}
return null;
}
public static ListNode merge(ListNode n1, ListNode n2) {
if (n1 == null) return n2;
if (n2 == null) return n1;
if (n1.val < n2.val) {
n1.next = merge(n1.next, n2);
return n1;
} else {
n2.next = merge(n1, n2.next);
return n2;
}
}
}