**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. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */

**Merge-Sort Approach**

Edit Merge k Sorted Lists on GitHub

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) heap.add(list); } ListNode head = new ListNode(0); 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) heap.add(temp.next); p = p.next; } return head.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.