Merging K Sorted Lists: Solving Coding Interview Question

In this post, we will look at another popular coding interview question.

Problem Statement

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.

Solution

A naive approach would be to merge them one by one, but that’s not efficient enough.

The Optimal Approach: Using a Priority Queue

We can use a priority queue (or min heap) to efficiently merge these sorted lists. A min heap allows us to always have the smallest element at the top. By inserting the first element of each list into the min heap along with its associated information, we can build our sorted list one element at a time.

Here’s the strategy:

1. Create a Min Heap: We’ll use a priority queue to store the first element of each list, along with the information about which list and position it came from.
2. Extract the Minimum: By extracting the top of the min heap, we get the smallest element and its information.
3. Insert the Next Element: Once we take an element from a list, we’ll insert the next element from the same list into the min heap.
4. Repeat: Continue until the min heap is empty.

Java Solution

import java.util.PriorityQueue;

public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Priority Queue with custom comparator to sort based on the node's value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);

        // Add the first node of each list to the priority queue
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        // Dummy head of the resulting linked list
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // Continue until the heap is empty
        while (!minHeap.isEmpty()) {
            // Poll the smallest element
            ListNode node = minHeap.poll();

            // Add it to the new list
            tail.next = node;
            tail = tail.next;

            // If there is another element in the same original list, add it to the heap
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

How Does the Code Work?

1. Initialization: We initialize a min heap with a custom comparator to sort based on the linked list node’s value.
2. First Element of Each List: We add the first node of each list into the min heap.
3. Building the Sorted List: While the min heap is not empty, we:
   - Poll the smallest element
   - Add it to the new sorted list
   - If there is another element in the original list it came from, we add it to the min heap.
4. Return Result: Finally, we return the sorted list, which is formed by linking all the nodes extracted from the min heap.

This solution is optimal with time complexity O(n log⁡k), where n is the total number of elements, and k is the number of lists. The priority queue ensures that we efficiently find the next smallest element.

Follow me on Medium, if you found this post helpful!