MANG Problem #4: Merge K Sorted Lists (Hard)

1. 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.

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

2. Approach: Min-Heap Optimization

graph TD
    subgraph "Min-Heap (K Nodes)"
        Smallest((Smallest Node))
        N1((Head 1))
        N2((Head 2))
        N3((Head 3))
    end
    
    Smallest --> Result[Result List]
    NextNode[Next node from same list] --> Min-Heap

The Naive Way (O(N*K))

Merge lists one by one. Merge List 1 and 2, then merge the result with List 3.

Why it fails: Too much redundant comparison. $N$ is the total number of nodes, $K$ is the number of lists.

The Optimized Way: Min-Heap (O(N log K))

We only ever need to compare the heads of each list. By keeping the heads in a Min-Heap (Priority Queue), we can find the smallest element in $O(\log K)$ time.

3. Java Implementation

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    
    // Custom comparator to sort nodes by value
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    // 1. Push the head of every list into the heap
    for (ListNode node : lists) {
        if (node != null) pq.offer(node);
    }
    
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    
    // 2. Extract min and push next node from that list
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = tail.next;
        
        if (node.next != null) {
            pq.offer(node.next);
        }
    }
    
    return dummy.next;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Think of this as a tournament. You have $K$ teams (lists), and you only need to know who the current champion is. You don't need to re-evaluate everyone; just replace the previous champion with their successor from the same team.
The Priority Queue: Java's PriorityQueue is a Min-Heap. It ensures that poll() always gives the smallest node in the queue.
The Pointer Surgery: We use a dummy node to avoid null-checks when starting the result list.

5. Interview Discussion

Interviewer: "What is the space complexity?"
You: "O(K) because the heap only ever stores one node from each of the $K$ lists at any given time."
Interviewer: "Can we do this without a heap?"
You: "Yes, using Divide and Conquer. We can merge pairs of lists (like Merge Sort). It has the same O(N log K) time but O(1) space if done iteratively."