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.

/**
 * 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.