Leetcode 23 Merge k Sorted Lists

Leetcode 23 Merge k Sorted Lists

The problem description is as follow:

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

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/```

It is quite intuitive to think about merge-sort. This problem is a simple transform of the original merge sort problem. We just have to divide those k sorted lists into smaller groups, and do the sort and merge.

```public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return mergeSort(lists,0,lists.length-1);
}
private ListNode mergeSort(ListNode[] lists, int l, int r) {
if(l<r) {
int m = (l+r)/2;
return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
}
return lists[l];
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
dummy.next = l1;
ListNode cur = dummy;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
l1 = l1.next;
}
else {
ListNode next = l2.next;
cur.next = l2;
l2.next = l1;
l2 = next;
}
cur = cur.next;
}
if(l2!=null)
cur.next = l2;
return dummy.next;
}
}```

Similar to the analysis in Leetcode 148 Sort List, assume the maximum length of every list is `n`, the time complexity is function `T(k)`, then we have `T(k) = T(k/2) + O(n*k)`.

According to Master Theorem,  `T(k) = O(n*klogk)`. The space complexity is  `O(logk)`, which is the depth of our recursive call.

Heap Approach

We can maintain a heap of size k and use heap-sort to return the smallest number in heap.

```1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size.
4. Pop a new smallest number ...```

Note that we can implement the heap with `PriorityQueue` in Java:

```public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;

//PriorityQueue is a heap that use heap-sort
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val-b.val;
}
});

//add first node of each list to the heap
for (ListNode list : lists) {
if (list != null)
}

ListNode p = head; // serve as a helper dummy node

while (heap.size() > 0) {
ListNode temp = heap.poll();
//poll() retrieves and removes the head of the heap
p.next = temp;

//keep adding next element of each list
if (temp.next != null)

p = p.next;
}

}
}```

In case you are not familiar with Heap and HeapSort:

• Get the smallest element in the heap requires `O(1)`
• Put a new element in the heap of size k requires `O(k)`

Since we have `n*k` elements in total, the total time complexity will be `O(nk*logk)`. The space complexity will be the size of heap `O(k)`.

Further Thoughts

Using heap to get the smallest/biggest single number or top K biggest/smallest numbers is very useful in real life, especially in big data area. If you want to know the hottest 10 topics, musics in billions of them, maintaining a heap is one of the best ways to do it. I will further discuss this problem in the future.