Merge K Sorted Lists — K-Way Merge with a Min-Heap

Problem Statement#

Given an array of k sorted linked lists, merge them into one sorted linked list and return its head.

Constraints:

• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= Node.val <= 10^4
• The sum of lists[i].length is at most 10^4

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

Input:  []
Output: []

Why This Problem Matters#

Merge K Sorted Lists is the highest-frequency heap FAANG question on LeetCode. Amazon and Google ask it specifically because it tests both data-structure intuition and pointer manipulation. It also models real production work — merging sorted shards from databases, log files, or distributed indexes.

The brute force is O(Nk): compare all k heads on every step. The optimal heap-based solution is O(N log k) and is the foundation for problems like Smallest Range Covering K Lists and external sort.

The Core Insight#

We always need the smallest unconsumed value across k sorted lists. A min-heap of size k holds one node per list. After popping the min, push its next pointer if it exists. The heap stays size-k throughout.

Visual Dry Run#

For lists [1,4,5], [1,3,4], [2,6]:

Solution (Optimal)#

import heapq
 
class Solution:
    def mergeKLists(self, lists):
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        dummy = tail = ListNode(0)
        while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

var mergeKLists = function(lists) {
    const heap = new MinHeap((a, b) => a.val - b.val);
    for (const head of lists) if (head) heap.push(head);
    const dummy = new ListNode(0);
    let tail = dummy;
    while (heap.size()) {
        const node = heap.pop();
        tail.next = node;
        tail = node;
        if (node.next) heap.push(node.next);
    }
    return dummy.next;
};

Time: O(N log k) — N total nodes, each pushed and popped once at log k cost. Space: O(k) — the heap holds at most one node per list.

Common Mistakes#

• Pushing every node up front instead of only k heads — turns it into O(N log N)
• Forgetting the tiebreaker (list index) in Python — comparing ListNode objects directly raises TypeError
• Mutating tail incorrectly and creating a cycle
• Skipping the empty-list filter on the initial seed
• Using O(Nk) divide-and-conquer recursion without realizing the heap is simpler

Interview Tips#

• Mention three approaches up front: brute force O(Nk), divide and conquer O(N log k), heap O(N log k) — heap is cleanest
• Use a tuple (val, index, node) to make ties deterministic
• Discuss memory: heap of k matters when k is huge and lists are short
• Variation: input is k arrays, not lists — same code, just track indices

Follow-up Questions#

• Sort k arrays instead of lists? Same heap approach with (value, array_id, position) tuples
• Streaming version where lists arrive one at a time? Use a leftist heap or pairing heap to allow heap-merge
• Find the smallest range covering one element from each list — see LeetCode 632
• External merge sort with k = 1000? Same idea, with file-backed iterators
• What if values can be equal? Tiebreaker keeps order stable

Key Takeaways#

• Min-heap of k heads turns O(Nk) into O(N log k)
• Always push only one element per list at a time — that bounds heap size to k
• Use a tuple with a tiebreaker in Python to avoid object comparison errors
• Foundation for k-way merge, external sort, and Smallest Range problems
• Divide-and-conquer pairwise merging hits the same complexity but uses more code
• Top heap FAANG question — memorize the template
• Real-world relevance: log merging, database shard merging, search index merging