-
Notifications
You must be signed in to change notification settings - Fork 35
/
43--merge-k-sorted-lists.java
32 lines (32 loc) · 1.07 KB
/
43--merge-k-sorted-lists.java
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
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
if (n == 0) return null;
int interval = 1;
while (interval < n) { // O(log k)
for (int i = 0; i + interval < n; i = i + interval * 2) {
lists[i] = mergeTwoSortedLists(lists[i], lists[i + interval]); // O(n)
}
interval = 2 * interval;
}
return lists[0];
}
public ListNode mergeTwoSortedLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode curr = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
curr.next = list1;
curr = curr.next;
list1 = list1.next;
} else {
curr.next = list2;
curr = curr.next;
list2 = list2.next;
}
}
if (list1 == null) curr.next = list2;
if (list2 == null) curr.next = list1;
return head.next;
}
} // TC: O(n * log k) , SC: O(1)