Merge k Sorted Lists (LeetCode 23)
You're given lists, an array holding k linked lists, where each individual list is already sorted from smallest to largest.
Combine every node from all k lists into a single linked list that is itself sorted from smallest to largest, and return its head.
Worked Examples
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]lists = [][]lists = [[]][]⚖️Formal Constraints & Bounds
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.The sum of
lists[i].lengthwill not exceed104.
Core Insight
The min-heap always contains at most K items, reducing the cost of finding the next minimum element from O(K) to O(log K).
Real-World Scenario & Production Applications
External merge sort in database query engines (PostgreSQL/DuckDB spilling to disk) and distributed log stream aggregation.
Subproblems & Recurrence Decomposition3 Phases
Push the head node of each of the K sorted linked lists into a min-heap (node.val, list_idx, node) in O(K log K) time.
min_heap = []
for i, head in enumerate(lists):
if head:
heappush(min_heap, (head.val, i, head))Step-by-Step Execution Trace Table
| Step | Heap Frontier (val, list, index) | Popped Element | Merged List Output | Next Refilled Element |
|---|---|---|---|---|
| 1 | (1,A,0), (1,B,0), (2,C,0) | (1, A, 0) | [1] | (4, A, 1) |
| 2 | (1,B,0), (2,C,0), (4,A,1) | (1, B, 0) | [1, 1] | (3, B, 1) |
| 3 | (2,C,0), (3,B,1), (4,A,1) | (2, C, 0) | [1, 1, 2] | (6, C, 1) |
| 4 | (3,B,1), (4,A,1), (6,C,1) | (3, B, 1) | [1, 1, 2, 3] | (4, B, 2) |
| 5 | (4,A,1), (4,B,2), (6,C,1) | (4, A, 1) | [1, 1, 2, 3, 4] | (5, A, 2) |
| 6 | (4,B,2), (5,A,2), (6,C,1) | (4, B, 2) | [1, 1, 2, 3, 4, 4] | List B exhausted None |
| 7 | (5,A,2), (6,C,1) | (5, A, 2) | [1, 1, 2, 3, 4, 4, 5] | List A exhausted None |
| 8 | (6,C,1) | (6, C, 1) | [1, 1, 2, 3, 4, 4, 5, 6] | All lists exhausted Done |
| 1 | heap = [(node.val, i, node) for i, node in enumerate(lists) if node] |
| 2 | dummy = ListNode(0) |
| 3 | curr = dummy |
| 4 | while heap: |
| 5 | val, i, node = heappop(heap) |
| 6 | curr.next = node |
| 7 | curr = curr.next |
| 8 | if node.next: |
| 9 | heappush(heap, (node.next.val, i, node.next)) |
| 10 | return dummy.next |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Merging $K$ pre-sorted linked lists generalizes the 2-way merge from Merge Sort. Rather than comparing all $K$ list heads on every step in $O(K)$ time, we place the active head node of each list into a min-heap of size $K$. Extracting the root yields the globally smallest unmerged node in $O(\log K)$ time. Appending its successor `curr.next` back to the heap maintains the multi-way stream frontier until all lists are exhausted in $O(N \log K)$ total time. 🃏 The Analogy: Merging k Decks of Cards
Imagine k separate decks of cards, each already sorted face-up. To merge them into one sorted pile, you only ever need to look at the top card of each deck — the smallest visible card across all k decks is guaranteed to be the smallest card not yet placed anywhere. Take it, place it on your output pile, then flip over the next card in whichever deck you just took from. Repeat until every deck is empty.
🔑 The Key Idea in the Code
The heap never holds more than k nodes at once — it's not merging all N nodes at once, only ever comparing the current "frontier" (one candidate per list), which is what keeps this O(N log K) instead of O(N·K).
Python 3
TypeErroron duplicate node values: Storing(node.val, node)in Python'sheapqraisesTypeError: '<' not supported between instances of 'ListNode'when two nodes have identical.val. Store(node.val, index, node)as a unique tie-breaker.Empty input list or list with null heads: Guarding
lists = []and filtering out empty list heads (None) before seeding the min-heap.Advancing node pointer without pushing
node.next: After extracting minimum node, you must pushnode.nextinto the heap ifnode.next is not None.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Merge K independently sorted linked lists.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: pop (val, i, node), link it after curr, and push node.next from the same list i. A list advances only when its own head is used, so the output stays sorted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Node comparison failure in Python heap: store tuple
(node.val, list_index, node)to prevent comparing ListNode objects.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a K-Way Merge. The smallest node left overall is always the head of one of the lists, so I keep just one head per list in a min-heap, as value, list index and node. I pop the smallest, link it after my tail, and push the next node from that same list, so each list advances only when its own head is used and the output stays sorted. A dummy head means the first node needs no special case, and I skip empty lists. The trap is ties: I put the list index in each tuple, so equal values never make Python compare two nodes, which would crash. Every node is pushed and popped once, so time is
O(N log K)for N nodes in total, and the heap needs O(K) space."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Min-heap stores current head of each of the K sorted linked lists. At each step, extracts min node in O(log K) and pushes next node in that list in O(log K). Total N nodes processed.
O(K) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Min-heap stores at most K list node references simultaneously.
T(N, K) = N · O(log K) = O(N log K)
Derivation Progression
K list heads ⟹ O(K log K)
Initializes min-heap with heads of all K lists.
N total nodes × O(log K) heappop/heappush
Appends smallest node to merged list in O(log K).
O(N log K)
Every node in all lists is pushed and popped exactly once.
Variable Definitions
Total number of nodes across all linked lists combined
Number of sorted linked lists (min-heap capacity)
Memory Architecture & Bounds
O(1) Iterative
O(K) Min-heap of size K
O(1) Merged linked list head (in-place pointer splicing)
Boundary Best / Worst Cases
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "merge k sorted linked lists": every node must come out, in order. Merging the lists one after another costs , = total nodes. A K-Way Merge keeps one head per list in a min-heap, so each node costs .
, total nodes . Time budget: . Memory budget: heap elements at any moment.
With up to lists, many short or empty, the heap is filled once with every non-empty head: an empty list is None and has no .val, so it must be skipped. When the lists are real streams (files, network readers), each is read in order and only its current head is held, so open inputs, not values, are the memory cost.
Core Algorithmic State Invariants
- Relink the Nodes, Don't Copy Them
curr.next = node reuses the popped node itself, so the merged list is built from the input nodes with no new allocations. The dummy sentinel gives curr somewhere to start, so the first node needs no special case, and dummy.next is the merged head.
Merge k Sorted Lists (LeetCode 23)
You're given lists, an array holding k linked lists, where each individual list is already sorted from smallest to largest.
Combine every node from all k lists into a single linked list that is itself sorted from smallest to largest, and return its head.
Worked Examples
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]lists = [][]lists = [[]][]⚖️Formal Constraints & Bounds
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.The sum of
lists[i].lengthwill not exceed104.
Core Insight
The min-heap always contains at most K items, reducing the cost of finding the next minimum element from O(K) to O(log K).
Real-World Scenario & Production Applications
External merge sort in database query engines (PostgreSQL/DuckDB spilling to disk) and distributed log stream aggregation.
Subproblems & Recurrence Decomposition3 Phases
Push the head node of each of the K sorted linked lists into a min-heap (node.val, list_idx, node) in O(K log K) time.
min_heap = []
for i, head in enumerate(lists):
if head:
heappush(min_heap, (head.val, i, head))Step-by-Step Execution Trace Table
| Step | Heap Frontier (val, list, index) | Popped Element | Merged List Output | Next Refilled Element |
|---|---|---|---|---|
| 1 | (1,A,0), (1,B,0), (2,C,0) | (1, A, 0) | [1] | (4, A, 1) |
| 2 | (1,B,0), (2,C,0), (4,A,1) | (1, B, 0) | [1, 1] | (3, B, 1) |
| 3 | (2,C,0), (3,B,1), (4,A,1) | (2, C, 0) | [1, 1, 2] | (6, C, 1) |
| 4 | (3,B,1), (4,A,1), (6,C,1) | (3, B, 1) | [1, 1, 2, 3] | (4, B, 2) |
| 5 | (4,A,1), (4,B,2), (6,C,1) | (4, A, 1) | [1, 1, 2, 3, 4] | (5, A, 2) |
| 6 | (4,B,2), (5,A,2), (6,C,1) | (4, B, 2) | [1, 1, 2, 3, 4, 4] | List B exhausted None |
| 7 | (5,A,2), (6,C,1) | (5, A, 2) | [1, 1, 2, 3, 4, 4, 5] | List A exhausted None |
| 8 | (6,C,1) | (6, C, 1) | [1, 1, 2, 3, 4, 4, 5, 6] | All lists exhausted Done |
| 1 | heap = [(node.val, i, node) for i, node in enumerate(lists) if node] |
| 2 | dummy = ListNode(0) |
| 3 | curr = dummy |
| 4 | while heap: |
| 5 | val, i, node = heappop(heap) |
| 6 | curr.next = node |
| 7 | curr = curr.next |
| 8 | if node.next: |
| 9 | heappush(heap, (node.next.val, i, node.next)) |
| 10 | return dummy.next |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Merging $K$ pre-sorted linked lists generalizes the 2-way merge from Merge Sort. Rather than comparing all $K$ list heads on every step in $O(K)$ time, we place the active head node of each list into a min-heap of size $K$. Extracting the root yields the globally smallest unmerged node in $O(\log K)$ time. Appending its successor `curr.next` back to the heap maintains the multi-way stream frontier until all lists are exhausted in $O(N \log K)$ total time. 🃏 The Analogy: Merging k Decks of Cards
Imagine k separate decks of cards, each already sorted face-up. To merge them into one sorted pile, you only ever need to look at the top card of each deck — the smallest visible card across all k decks is guaranteed to be the smallest card not yet placed anywhere. Take it, place it on your output pile, then flip over the next card in whichever deck you just took from. Repeat until every deck is empty.
🔑 The Key Idea in the Code
The heap never holds more than k nodes at once — it's not merging all N nodes at once, only ever comparing the current "frontier" (one candidate per list), which is what keeps this O(N log K) instead of O(N·K).
Python 3
TypeErroron duplicate node values: Storing(node.val, node)in Python'sheapqraisesTypeError: '<' not supported between instances of 'ListNode'when two nodes have identical.val. Store(node.val, index, node)as a unique tie-breaker.Empty input list or list with null heads: Guarding
lists = []and filtering out empty list heads (None) before seeding the min-heap.Advancing node pointer without pushing
node.next: After extracting minimum node, you must pushnode.nextinto the heap ifnode.next is not None.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Merge K independently sorted linked lists.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: pop (val, i, node), link it after curr, and push node.next from the same list i. A list advances only when its own head is used, so the output stays sorted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Node comparison failure in Python heap: store tuple
(node.val, list_index, node)to prevent comparing ListNode objects.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a K-Way Merge. The smallest node left overall is always the head of one of the lists, so I keep just one head per list in a min-heap, as value, list index and node. I pop the smallest, link it after my tail, and push the next node from that same list, so each list advances only when its own head is used and the output stays sorted. A dummy head means the first node needs no special case, and I skip empty lists. The trap is ties: I put the list index in each tuple, so equal values never make Python compare two nodes, which would crash. Every node is pushed and popped once, so time is
O(N log K)for N nodes in total, and the heap needs O(K) space."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Min-heap stores current head of each of the K sorted linked lists. At each step, extracts min node in O(log K) and pushes next node in that list in O(log K). Total N nodes processed.
O(K) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Min-heap stores at most K list node references simultaneously.
T(N, K) = N · O(log K) = O(N log K)
Derivation Progression
K list heads ⟹ O(K log K)
Initializes min-heap with heads of all K lists.
N total nodes × O(log K) heappop/heappush
Appends smallest node to merged list in O(log K).
O(N log K)
Every node in all lists is pushed and popped exactly once.
Variable Definitions
Total number of nodes across all linked lists combined
Number of sorted linked lists (min-heap capacity)
Memory Architecture & Bounds
O(1) Iterative
O(K) Min-heap of size K
O(1) Merged linked list head (in-place pointer splicing)
Boundary Best / Worst Cases
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "merge k sorted linked lists": every node must come out, in order. Merging the lists one after another costs , = total nodes. A K-Way Merge keeps one head per list in a min-heap, so each node costs .
, total nodes . Time budget: . Memory budget: heap elements at any moment.
With up to lists, many short or empty, the heap is filled once with every non-empty head: an empty list is None and has no .val, so it must be skipped. When the lists are real streams (files, network readers), each is read in order and only its current head is held, so open inputs, not values, are the memory cost.
Core Algorithmic State Invariants
- Relink the Nodes, Don't Copy Them
curr.next = node reuses the popped node itself, so the merged list is built from the input nodes with no new allocations. The dummy sentinel gives curr somewhere to start, so the first node needs no special case, and dummy.next is the merged head.