Merge k Sorted Lists

Two ideas to solve this problem.

1: Split the k sorted lists into 2 lists, until you reach 1 or 2 list, and then merge the two list (I did this before but I almost totally forgot, need recap.. T_T). Just like the merge sort.
Run time analysis:
T(k) = 2T(k/2)(split) + n*k(merge) according to master’s theorem, n is a constant to k, so case 2, and T(k) = nklogk. The space complexity is the run time stack, which is the hight of the split tree, and it is logk.

2: Maintain a priority queue (min heap) of size k. First we stick the first nodes of every list in to the heap. Then we remove the node from the heap top, and put the next node of the removed node into the heap to replace the removed one. This way we maintain a heap that contains the first node of the current list, and form the result list by removing the heap top.

Run time analysis:
To scan all the elements will take n*k time, and each element takes logk time to maintain the min-heap. So the total run time is also nklogk. The space complexity is the size of the heap, O(k)

method 1:
notice that we need only one pointer to merge 2 sorted list. Also notice the use of the subList(fromIndex(inclusive), toIndex(exclusive)). The subList API only works for list, so need to use the arrayList constructor.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        if (lists.size() == 1)
            return lists.get(0);
        if (lists.size() == 2)
            return merge(lists.get(0), lists.get(1));
        // just like merge sort, split the list into half and recursive
        
        ListNode list1 = mergeKLists(new ArrayList<ListNode>(lists.subList(0, lists.size()/2)));
        ListNode list2 = mergeKLists(new ArrayList<ListNode>(lists.subList(lists.size()/2, lists.size())));
        return merge(list1, list2);
    }
    
    public ListNode merge(ListNode n1, ListNode n2) {// merge two sorted list
        if (n1 == null)
            return n2;
        if (n2 == null)
            return n1;
        ListNode head = (n1.val < n2.val)?n1 : n2; // for return result
        ListNode tail = new ListNode(0); // helper for easy operation
        while(n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                tail.next = n1;
                n1 = n1.next;
            }
            else {
                tail.next = n2;
                n2 = n2.next;
            }
            tail = tail.next;
        }
        if (n1 == null) // rest elements all from n2
            tail.next = n2;
        if (n2 == null) // rest elements all from n1
            tail.next = n1;
        return head;
    }
}

method 2:

recap the use of the priority queue as min heap. treat the corner case of empty list and empty node as the list element

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        if (lists.size() == 1)
            return lists.get(0);
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){ // anonymous class, need to put init capacity as the first arg
                @Override
                public int compare(ListNode n1, ListNode n2) {
                    if (n1.val > n2.val)
                        return 1;
                    if (n1.val < n2.val)
                        return -1;
                    return 0;
                }
        });
        for (ListNode n : lists) {
            if (n != null)
                queue.add(n);
        }
        ListNode head = queue.peek();
        ListNode tail = new ListNode(0);
        while(!queue.isEmpty()) {
            tail.next = queue.remove();
            tail = tail.next;
            if (tail.next != null)
                queue.add(tail.next);
        }
        return head;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s