L25: Merge K Sorted Lists | Multiple Approaches

1. Problem Statement & Overview

When tackling the problem of Merging $K$ Sorted Lists, you are given $K$ distinct linked lists, each already sorted in ascending order. Your task is to combine all integer values from every list, merge them into a single sorted sequence, and return the head of the new merged linked list.

To understand the scale of optimization, let us assume a hypothetical uniformity: each of the $K$ linked lists has an average length of $N$. This implies the total number of nodes across all lists combined is $M = K \times N$.

2. Approach 1: The Brute Force Method (Array Extraction & Sorting)

Core Mental Model

The most naive, intuitive approach is to completely ignore the linked structure initially. Treat the lists simply as containers of raw numbers, dump every single integer into a linear array, sort that array using a standard sorting algorithm, and then rebuild a brand-new linked list from the sorted array elements.

Step-by-Step Evolution

1. Initialize an empty array: Create a dynamic array or list to hold all integer values.
2. Traverse all lists: Iterate through the list of heads from index $0$ to $K-1$. For each list, traverse from its head node to the end, appending each node's data value to your array.
3. Sort the array: Call a standard sorting utility on the array (taking $O(M \log M)$ time where $M = K \times n$).
4. Reconstruct linked list: Pass the sorted array through a helper function (convert array to linked list) which links the sorted integers together and returns the head of the newly forged list.

Pseudo-Code

def mergeKLists_BruteForce(lists):
    arr = []
    # Step 1: Extract all elements into an array
    for i in range(len(lists)):
        temp = lists[i]
        while temp is not None:
            arr.append(temp.data)
            temp = temp.next
            
    # Step 2: Sort the master array
    arr.sort()
    
    # Step 3: Convert sorted array back to a linked list
    new_head = convertArrayToLinkedList(arr)
    return new_head

Complexity Analysis

• Time Complexity: $O(K \cdot N + (K \cdot N)\log(K \cdot N) + K \cdot N)$
  • Traversal takes $O(K \cdot N)$ where each list has size $N$.
  • Sorting $M$ elements ($M = K \cdot N$) takes $O(M \log M)$.
  • Conversion back to a linked list takes $O(M)$.
• Space Complexity: $O(K \cdot N)$ auxiliary space is required to store all integer elements in the array, plus another $O(K \cdot N)$ space to build the new linked list nodes.

3. Approach 2: The Better Approach (Iterative Pairwise Merging in-place)

Core Mental Model

Instead of allocating extra arrays and rebuilding new nodes, we can leverage our knowledge from Merging Two Sorted Lists (a prerequisite concept). We take the accumulated list so far and merge it with the next list sequentially.

Real-Life Analogy

Imagine organizing a tournament or a card game where you have $K$ separated stacks of sorted cards. Instead of dumping all cards on the floor, you take Stack 1, merge it with Stack 2 to form a combined sorted pile. Then, you take that combined pile and merge it with Stack 3, and so on, until all cards form a single sorted stack.

Step-by-Step Flow

Pseudo-Code

def mergeKLists_Iterative(lists):
    if not lists or len(lists) == 0:
        return None
        
    head = lists[0]
    
    # Iteratively merge each subsequent list with our running merged head
    for i in range(1, len(lists)):
        head = mergeTwoLists(head, lists[i])
        
    return head

Complexity Analysis & Performance Bottlenecks

• Time Complexity: As we accumulate nodes, the length of our running merged list grows: $N$, then $2N$, then $3N$, all the way up to $K \cdot N$.
  • Summing the merge costs: $N + 2N + 3N + \dots + K \cdot N = N \cdot (1 + 2 + 3 + \dots + K) = N \cdot \frac{K(K+1)}{2} \approx O(N \cdot K^2)$.
  • If $K$ is large, this approaches cubic time complexity order ($O(K^3)$ if $K \approx N$).
• Space Complexity: $O(1)$ auxiliary space, because we perform in-place pointer modifications without allocating new nodes.

4. Approach 3: The Optimal Solution (Min-Heap / Priority Queue)

Core Mental Model

To achieve the absolute optimal time complexity, we must stop comparing lists one-by-one linearly. At any given moment in our final sorted list, the next smallest element must be the absolute minimum among the current heads of all remaining active lists. A Min-Heap (Priority Queue) is the exact data structure designed to track running minimums dynamically in logarithmic time.

Real-Life Analogy

Think of $K$ separate post office windows ($K$ sorted lists), where each window only shows its next person in line. Instead of looking at every single person in every line, you place a digital manager (the Priority Queue) at the front. The manager always tells you instantly: "Here is the person with the smallest number across all $K$ window fronts." Once that person is served, the window sends the next person in line up to the front.

Step-by-Step Flow Walkthrough

1. Initialize a Min-Heap: Store pairs of (node.value, node) ordered by the integer value.
2. Seed the Heap: Iterate through all list heads. If a head is not null, push its (value, node) pair into the priority queue.
3. Setup Dummy Node: Create a dummy node and a temporary pointer to construct our result list cleanly without edge-case head checks.
4. Extract and Replenish Loop:
   • While the priority queue is not empty:
     • Extract the minimum element (top).
     • Attach this node to temporary.next.
     • Advance temporary forward.
     • If the extracted node has a .next neighbor in its original list, push that next node into the priority queue.
5. Return Result: Return dummy.next.

Step-by-Step Execution Table (Mini Simulation)

Suppose we have 3 lists with heads holding values [2], [1], [4].

5. Complete Optimal Implementation (C++ Reference)

Here is the production-ready code demonstrating how the optimal Min-Heap approach is structured using C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // Define a min-heap priority queue storing pairs of {value, node pointer}
        // Using greater<> to ensure minimum element stays at the top
        priority_queue<pair<int, ListNode*>, 
                       vector<pair<int, ListNode*>>, 
                       greater<pair<int, ListNode*>>> pq;
        
        // Step 1: Push the head of every non-null list into the priority queue
        for(int i = 0; i < lists.size(); i++) {
            if(lists[i] != nullptr) {
                pq.push({lists[i]->val, lists[i]});
            }
        }
        
        // Step 2: Create a dummy node to build the result list
        ListNode* dummyNode = new ListNode(-1);
        ListNode* temp = dummyNode;
        
        // Step 3: Extract minimums and replenish from respective lists
        while(!pq.empty()) {
            auto it = pq.top();
            pq.pop();
            
            int val = it.first;
            ListNode* node = it.second;
            
            // Attach node to our resulting merged list
            temp->next = node;
            temp = temp->next;
            
            // If there is a next node in the current list, push it into the min-heap
            if(node->next != nullptr) {
                pq.push({node->next->val, node->next});
            }
        }
        
        return dummyNode->next;
    }
};

6. Comparative Approach Synthesis

7. Summary and Key Takeaways

• Problem Reduction: Merging $K$ sorted structures is a foundational pattern that scales from merging 2 lists to handling streaming data from $K$ independent sources.
• Brute Force Inefficiencies: Dumping all elements into an array and sorting incurs heavy overhead in both time and memory ($O(M \log M)$ and $O(M)$ extra space).
• In-Place Advantage: The iterative pairwise approach saves memory space ($O(1)$ auxiliary space) by rewiring pointers, but degrades to $O(K^2 \cdot N)$ time complexity.
• The Power of Heaps: A Min-Heap / Priority Queue maintains the smallest candidates across all $K$ lists simultaneously, bounding selection overhead to $O(\log K)$ per operation.
• Overall Optimal Complexity: By using a priority queue, the total time complexity drops to $O(N \cdot K \log K)$ with an auxiliary space complexity of just $O(K)$ for the heap storage.