Merge K Sorted Lists — Min-Heap and Divide & Conquer Explained

Problem Statement#

LeetCode 23 — Merge k Sorted Lists Difficulty: Hard | Pattern: Min-Heap / Divide and Conquer

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

Constraints:

• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• Total nodes: at most 10^4
• -10^4 <= Node.val <= 10^4
• Each list is sorted in ascending order.

Example 1:

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

Example 2:

Input:  lists = []
Output: []

Example 3:

Input:  lists = [[]]
Output: []

Example 4:

Input:  lists = [[1],[0]]
Output: [0, 1]

Why This Problem Matters#

Merge K Sorted Lists is one of the most commonly asked hard problems at top tech companies. Amazon, Google, Facebook, Microsoft, and Uber regularly include it in phone screens and onsite interviews because it simultaneously tests:

• Knowledge of the min-heap (priority queue) data structure
• Ability to optimize from O(kN) naive merging to O(N log k)
• Understanding of divide-and-conquer applied to linked lists
• Code quality under pressure — correctly managing heap comparators and dummy head nodes

The problem has direct real-world parallels: merging sorted database query results, combining sorted log files, external merge sort (used when data is too large for memory), and K-way merge in distributed systems. Any candidate who can articulate the O(N log k) solution with either a heap or divide-and-conquer and explain why it is better than naive merging demonstrates strong algorithmic thinking.

The naive approach — merge two lists at a time sequentially — runs in O(kN) because each of the N total nodes is touched up to k times. Both optimal approaches reduce this to O(N log k) by making each node participate in only log k comparisons.

The Core Insight#

Min-Heap approach: At any point, you need the minimum value across all k list heads. A min-heap of size k gives you the minimum in O(log k) time. Process N total nodes, each requiring one heap push and one heap pop: O(N log k) total.

Divide-and-conquer approach: Instead of merging k lists one by one (O(kN)), merge them pairwise. In round 1, merge k/2 pairs into k/2 lists. In round 2, merge those k/4 pairs. After log k rounds, you have one final merged list. Each round touches all N nodes once: O(N log k) total with O(log k) recursion depth.

Both approaches achieve the same asymptotic complexity. The heap approach has better practical performance for streaming data (you do not need all lists upfront). The divide-and-conquer approach has lower constant factors and can be implemented without the heap data structure.

Visual Dry Run#

Input: [[1,4,7], [2,5,8], [3,6,9]]

Min-Heap trace:

Initial heap: [(1, list0), (2, list1), (3, list2)]

Divide-and-conquer trace:

Round 1: merge(list0, list1) = [1,2,4,5,7,8]; list2 = [3,6,9] Round 2: merge([1,2,4,5,7,8], [3,6,9]) = [1,2,3,4,5,6,7,8,9]

Solution (Optimal)#

Approach 1: Min-Heap

import heapq
from typing import List, Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
 
    # Initialize heap with the head of each non-empty list
    # Use (val, index, node) — index breaks tie when vals are equal
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
 
    dummy = ListNode(0)
    curr = dummy
 
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
 
    return dummy.next

// Min-Heap approach using a simple priority queue
function mergeKLists(lists) {
    // Min-heap simulation using sorted insertion
    // (In real interviews, use a PriorityQueue class or library)
    const heap = [];
 
    const push = (node, idx) => {
        heap.push({ val: node.val, idx, node });
        heap.sort((a, b) => a.val - b.val); // simplification; use proper heap for O(log k)
    };
 
    for (let i = 0; i < lists.length; i++) {
        if (lists[i]) push(lists[i], i);
    }
 
    const dummy = { val: 0, next: null };
    let curr = dummy;
 
    while (heap.length > 0) {
        const { node } = heap.shift();
        curr.next = node;
        curr = curr.next;
        if (node.next) push(node.next, 0);
    }
 
    return dummy.next;
}

Approach 2: Divide and Conquer

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    def merge_two(l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next
 
    if not lists:
        return None
 
    # Iteratively merge pairs
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged
 
    return lists[0]

function mergeKLists(lists) {
    function mergeTwo(l1, l2) {
        const dummy = { val: 0, next: null };
        let curr = dummy;
        while (l1 && l2) {
            if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = l1 || l2;
        return dummy.next;
    }
 
    if (!lists || lists.length === 0) return null;
 
    while (lists.length > 1) {
        const merged = [];
        for (let i = 0; i < lists.length; i += 2) {
            const l1 = lists[i];
            const l2 = i + 1 < lists.length ? lists[i + 1] : null;
            merged.push(mergeTwo(l1, l2));
        }
        lists = merged;
    }
 
    return lists[0];
}

Complexity:

Common Mistakes#

1. Using (val, node) in Python heap when vals are equal: Python compares tuples element by element. If two nodes have the same val, Python tries to compare ListNode objects, which causes an error. Always include a tie-breaking index: (val, index, node).
2. Not handling empty lists or null nodes: Check if lists is empty before starting and if node before pushing to the heap.
3. Sequential merging instead of pairwise: Merging k lists one by one gives O(kN). Always use pairwise (divide-and-conquer) or heap approach for O(N log k).
4. Forgetting curr.next = l1 or l2 in merge_two: After the while loop, one list may have remaining nodes. Attach them directly instead of iterating through individually.
5. Advancing curr without setting curr.next first: In the heap approach, always set curr.next = node before advancing curr = curr.next.

Interview Tips#

• State both approaches upfront: "I know two O(N log k) approaches: a min-heap and divide-and-conquer. Let me start with the heap since it is more directly intuitive."
• Explain the O(N log k) argument: "N total nodes, each pushed and popped from the heap exactly once, each heap operation is O(log k). Total: O(N log k)."
• Show the tie-breaking trick: In Python, mention the (val, index, node) tuple explicitly. Interviewers who know Python will appreciate this.
• Offer divide-and-conquer as an upgrade: "The D&C approach has lower constant factors and avoids the heap entirely. It processes all N nodes in O(log k) rounds."
• Handle edge cases: "Empty lists, lists containing null heads, and a single list with one node — all handled by checking if node before pushing."

Follow-up Questions#

1. External merge sort: k = number of sorted file segments, N = total records. Same O(N log k) heap approach applies.
2. What if k is very large (e.g., 10^4)? The heap still works — it contains at most k nodes at a time. Heap operations are O(log k), so the total time stays O(N log k).
3. LeetCode 21 — Merge Two Sorted Lists: The base case for this problem — must be solid before tackling k-way merge.
4. What if lists could be infinitely long (streaming)? The heap approach handles infinite streams naturally — you only keep one node per list in memory.
5. Can you do better than O(N log k)? No — any comparison-based algorithm must do at least O(N log k) comparisons to merge k sorted lists.

Key Takeaways#

• Naive sequential merging is O(kN) — always use a heap or divide-and-conquer for O(N log k).
• Min-heap approach: Push each list's head into a size-k heap. Pop the minimum, append to output, push its successor. Each node is pushed and popped once: O(N log k) total.
• Divide-and-conquer: Pairwise merge k lists in log k rounds, each round processing all N nodes: O(N log k) total, O(log k) space.
• In Python, use (val, index, node) tuples in the heap to avoid comparison errors when node values are equal.
• The merge_two helper should handle the "attach remaining nodes" case with curr.next = l1 or l2 to avoid iterating the remaining list.
• This problem is the gateway to external merge sort, distributed data merging, and any real-world scenario involving k sorted data streams.