Problem · LC 23

Merge K Sorted Lists

Hard
◧ Advanced · priority queue / divide-and-conquer

How to recognize it

Given k sorted linked lists, merge them into one sorted list. The signal: "merge k lists", "combine multiple sorted lists". This is the hard version of merge-two-lists.

The core idea

Use a min-heap (priority queue) with size k. Insert the head of each list. Pop the smallest, add it to the result, and insert the next node from that list. Repeat until the heap is empty. Time: O(n log k) where n is total nodes.

Why It's Tricky

Merging k lists by repeatedly merging two lists is inefficient (would be O(n*k^2)). A heap lets you always access the global minimum efficiently. The trade-off: heap operations are O(log k) instead of comparing just two lists.

The Key Insight

A min-heap of size k processes the global minimum in O(log k) time. With n total nodes, we pop n times, so total is O(n log k). This is much better than O(nk) or merging pairwise.

Step-by-Step Walkthrough

Example: [[1,4,5],[1,3,4],[2,6]]

Heap: [1(list1), 1(list2), 2(list3)]
Pop 1: attach 1, push 4 from list1 → Heap: [1(list2), 2(list3), 4(list1)]
Pop 1: attach 1, push 3 from list2 → Heap: [2(list3), 3(list2), 4(list1)]
Pop 2: attach 2, push 6 from list3 → Heap: [3(list2), 4(list1), 6(list3)]
...
Result: 1→1→2→3→4→4→5→6

time O(n log k)
space O(k)
merge_k_sorted_lists
import heapq

def mergeKLists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, idx, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

Interview gotchas

  • Must handle empty lists: filter out null heads before inserting into heap.
  • Priority queue in Python is a min-heap by default; in other languages, you might need to negate values or use a custom comparator.
  • Each node can have up to k different lists; be careful not to revisit nodes.
  • Space complexity of heap: O(k) (only k heads in memory at a time).

💡 What to Say in the Interview

  • Say: "I'll use a min-heap to always process the global minimum efficiently."
  • Explain: "Insert the head of each list, pop the smallest, attach it, and insert the next from that list."
  • Complexity: "O(n log k) time — n nodes, log k per heap operation. Space: O(k) for the heap."
  • Alternative: "I could also divide-and-conquer: merge pairs repeatedly. Also O(n log k)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.