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

Example:

Input: [   1->4->5,   1->3->4,   2->6 ] 
Output: 1->1->2->3->4->4->5->6

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
    }
}

Problem Clarification

We are allowed to modify the given lists to produce the resultant merged list.

Idea - 1

We know how to merge two sorted lists. So, we apply the same idea k-1 times. Merge first and second lists. Merge the result with the third list and so on. Say each list has n nodes. There are then k-1 merges requiring time . The overall time complexity is and space .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k==0)
        {
            return null;
        }
        
        ListNode result = lists[0];
        for(int i = 1; i < k; ++i)
        {
            result = merge2(result, lists[i]);
        }
        
        return result;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 169 ms, faster than 12.22% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 51.3 MB, less than 5.05% of Java online submissions for Merge k Sorted Lists.

Idea - 2

Actually the first node in the result list must be the one among the heads of the k lists that has minimal value. Thus if we repeatedly pick the min from the k heads we have the merged list. To efficiently pick the min we use a minheap. Time and space .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> mq = new PriorityQueue<>(new Comparator<ListNode>()
                                                         {
                                                             public int compare(ListNode a, ListNode b)
                                                             {
                                                                 return a.val - b.val;
                                                             }
                                                         });
        
        for(ListNode head : lists)
        {
            if(head != null)
            {
                mq.offer(head);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(!mq.isEmpty())
        {
            ListNode min = mq.poll();
            t.next = min;
            t = t.next;
            
            if(min.next != null)
            {
                min = min.next;
                mq.offer(min);
            }
        }
        
        return dummy.next;
    }
}


Runtime: 5 ms, faster than 91.84% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 40.6 MB, less than 22.83% of Java online submissions for Merge k Sorted Lists.

Idea - 3

We can merger each pair of the given k lists as a result we have k/2 lists. We keep doing the same until we end up with a single list. Time complexity is . Space complexity is .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        
        if(k==0)
        {
            return null;
        }
        
        while(k > 1)
        {
            k = mergePairs(lists, k);
        }
        
        return lists[0];
    }
    
    private int mergePairs(ListNode[] lists, int n)
    {
        int i = 0;
        int j = 0;
        while(i < n-1)
        {
            lists[j++] = merge2(lists[i], lists[i+1]);
            i += 2;
        }
        
        if(i < n)
        {
            lists[j++] = lists[i];
        }
        
        return j;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 2 ms, faster than 99.90% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.5 MB, less than 12.95% of Java online submissions for Merge k Sorted Lists.