Merge k Sorted Lists

Given an array of k sorted linked lists, merge them into one sorted linked list.

Why this is worth learning

The provided reference is a heap-based k-way merge, not recursive pairwise merge. Both organize partial sorted streams, but their active state and auxiliary-space costs differ.

Before coding: one-minute experiment

For lists [1,4], [1,3], and [2], what can the initial heap contain, and what enters after removing the head of [1,4]?

Function signature

func MergeKLists(lists []*ListNode) *ListNode

Inputs / outputs

• lists: slice of sorted linked-list heads.
• Return: head of one sorted list containing all nodes.

Example

lists = [1->4->5, 1->3->4, 2->6]
Output: 1->1->2->3->4->4->5->6

Constraints

• 0 <= k <= 10_000
• Total node count can be large.

Core idea (near-solution)

Use a min-heap of current list heads. Pop the smallest node, append it to the output, then push its next node if present.

Invariant: the heap contains exactly the smallest not-yet-output node from each non-empty remaining list.

Algorithm (step-by-step)

1. Push every non-nil list head into a min-heap.
2. Create a dummy output head.
3. While the heap is non-empty:
   • Pop the node with the smallest value.
   • Append it to the result.
   • If that node has Next, push Next into the heap.
4. Return dummy.Next.

Correctness sketch

The heap contains the current smallest unconsumed node of each nonempty input stream. The smallest among those heads is globally smallest because every other node in each stream is at least its head. Removing that head, appending it, and inserting its successor preserves this frontier invariant. Each input node enters and leaves the heap once, so all nodes appear exactly once in sorted order. Input lists must be disjoint acyclic chains; shared tails would cause the same node identity to be scheduled multiple times and invalidate this argument. Equal values may be merged in any cross-list order.

Trace (hand walkthrough)

heap heads: 1(listA), 1(listB), 2(listC)
pop 1(A), push 4(A)
pop 1(B), push 3(B)
pop 2(C), push 6(C)
continue -> 1,1,2,3,4,4,5,6

Pitfalls to avoid

• Pushing all nodes at once when only heads are needed.
• Forgetting to push the popped node's successor.
• Losing nodes by overwriting Next before saving it.

Debugging lens

Capture/push a node’s successor before rewiring its output link. Verify every original pointer occurs once and the final tail is nil. Do not require a stable ordering across equal-valued nodes from different lists.

Complexity

Let N be total nodes, k the number of supplied heads, and h the number of nonempty lists. Time O(k + N log(h+1)); the initial head scan matters even when most lists are empty. Auxiliary heap space O(h), excluding the reused output nodes.

Implementation notes (Go)

• Implement heap.Interface over []*ListNode.
• Reuse existing nodes; no need to allocate new list nodes.

Contract precision

Input lists are individually sorted, acyclic, and node-disjoint. The reference reuses and rewires their nodes. Caller head-slice entries are retained, but the chains reachable from those heads can change.

Reconstruction checkpoint

For lists [1,4], [1,3], and [2], what can the initial heap contain, and what enters after removing the head of [1,4]?

Return to Divide & Conquer · Module quiz