[Google Question] Merge K Sorted Lists

Problem: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example:

Input: lists = [[1,2,3],[1,2,4],[2,5]]
Output: [1,1,2,2,2,3,4,5]

Approach: One simple approach would be to first look for the first nodes in all the lists, whichever has the minimum value, add that node to output and move this node to its next node. Repeat this till we have traversed all the nodes that means, all the nodes in the lists are null. Our algorithm will look like:

• MergeLists(lists)
• minNode = null;
• minIndex = -1
• For i = 0  to n - 1
• IF lists[i] != null
• IF minNode == null || minNode.Value > lists[i].Value
• minNode = lists[i];
• minIndex = i
• IF minNode != null
• lists[minIndex] = lists[minIndex].Next
• minNode.Next = MergeLists(lists)
• RETURN minNode

This will work and we can apply an optimization that if we found there in only one list is not null just return minNode in that case but its complexity is O(k * n) where k is the number of list and n is number of total nodes. Let's try to do better.

If you see to get the node with minimum value we are actually taking k steps. What if we use a Min-Heap /  Priority Queue of these k values. With the usage of min heap our algorithm will look like:

• For i = 0 to n-1
• IF lists[i] != null
• MinHeap.Add({lists[i].Value => lists[i]})
• head = null
• itr = head
• WHILE MinHeap not empty
• node = MinHeap.RemoveTop().Value
• IF head == null
• head = node
• itr = head
• ELSE
• itr.next = node
• itr = itr.next
• IF node.Next != null
• heap.Add({node.Next.Value => node.Next})
• itr.next = null
• RETURN head

I am using SortedDictionary in my implementation as C# has no default Heap. That's all!

Implementation in C#:

    public ListNode MergeKLists(ListNode[] lists) 

    {

        if (lists?.Length == 0)

        {

            return null;

        }

        SortedDictionary<int, List<ListNode>> heap = new SortedDictionary<int, List<ListNode>>();

        foreach (ListNode list in lists)

        {

            if (list != null)

            {

                if (!heap.ContainsKey(list.val))

                {

                    heap.Add(list.val, new List<ListNode>());

                }

                heap[list.val].Add(list);

            }

        }

        ListNode head = null;

        ListNode itr = null;

        while (heap.Count > 0)

        {

            List<ListNode> nodes = heap.First().Value;

            ListNode node = nodes.Last();

            nodes.RemoveAt(nodes.Count - 1);

            if (nodes.Count == 0)

            {

                heap.Remove(node.val);

            }

            if (head == null)

            {

                head = node;

                itr = head;

            }

            else

            {

                itr.next = node;

                itr = itr.next;

            }

            if (node.next != null)

            {

                if (!heap.ContainsKey(node.next.val))

                {

                    heap.Add(node.next.val, new List<ListNode>());

                }

                heap[node.next.val].Add(node.next);

            }

        }

        if (itr != null)

        {

            itr.next = null;

        }

        return head;

    }

Complexity: O(nlogk)