Merge K Sorted Lists

Problem

Database engines and distributed systems merge sorted partitions (from different shards or sort runs) into a single sorted result. This is the K-way merge problem: the naive approach collects everything and sorts, but a heap does it in O(n log K) by always knowing which list holds the next global minimum. Given k sorted linked lists, return one sorted merged linked list.

Example 1:

Input: lists = [[3->7->8], [3->4->7], [2->9]]
Output: 2->3->3->4->7->7->8->9
Explanation: the three sorted chains merge into one sorted chain.

Example 2:

Input: lists = []
Output: []
Explanation: there are no lists to merge, so the result is empty.

Example 3:

Input: lists = [[]]
Output: []
Explanation: the only list is empty, so the result is empty.

Constraints:

• 0 <= lists.length <= 10^3
• 0 <= lists[i].length <= 500
• -100 <= lists[i][j] <= 100
• lists[i] is sorted in ascending order.
• The sum of all lists[i].length does not exceed 10^4.

Solution Breakdown

Approach 1: K-way merge with a min-heap

Approach: K-way merge with a min-heap.

Each input list is already sorted, so at any moment the next node for the output is the smallest current head across the K lists. A min-heap finds that minimum in O(log K). Seed it with one entry per non-empty list as (node.val, i, node): the value drives ordering, and i (the list index) is a tie-breaker that stops Python from ever comparing two ListNode objects when values are equal - direct node comparison raises TypeError. Then loop: pop the smallest entry, splice its node onto the result via a dummy-head cursor, and if that node has a successor, push (node.next.val, i, node.next). Each pop emits the global minimum among all remaining heads, so the output is built in sorted order. The heap holds at most one node per list, and every node is pushed and popped exactly once.

The dummy head lets the first attachment use the same curr.next = node; curr = curr.next step as every other, with the merged list read off as dummy.next at the end.

Edge cases: an empty lists, or lists that are all None, push nothing, so the loop never runs and dummy.next is None. A list exhausting simply contributes no further pushes; the heap shrinks until empty.

Complexity: O(n log K) time, O(K) space - n total nodes, each an O(log K) heap operation against a heap bounded by the K list count.

Approach 2: Pairwise merge (divide and conquer)

There's a second approach that achieves the same O(n log K) time without a heap. Instead of tracking all K lists simultaneously, merge them in pairs - like the combine phase of merge sort applied to the list of lists:

1. Pair up adjacent lists: (list[0], list[1]), (list[2], list[3]), ...
2. Merge each pair with the standard two-pointer merge_two (the same routine from merge-two-sorted-lists).
3. The K lists become K/2 lists. Repeat until one list remains.

Each round touches every node once (O(n) total work across all pairs), and there are ⌈log₂ K⌉ rounds. Total: O(n log K) time, O(1) extra space (nodes are rewired in place - no heap allocation).

When to prefer pairwise over the heap:

• Cache locality: pairwise merge walks each list sequentially, which is cache-friendly. The heap jumps between lists on every pop, which is cache-hostile for large K.
• No tiebreaker needed: merge_two compares values directly - no list_index tuple hack.
• Simpler code: if you already have merge_two, the outer loop is 4 lines.
• When K is small and n is large: the constant factor of heap operations (sift-up/sift-down per node) can dominate; pairwise avoids per-node heap overhead.

When the heap wins:

• Streaming/online inputs: the heap processes nodes as they arrive (push one head per list up front); pairwise needs all lists available at once.
• Uneven list lengths: the heap drains short lists early and never touches them again; pairwise may re-walk already-merged material in later rounds.
• External sort: the heap is the standard final merge step because it reads one element per list at a time, minimizing I/O.

Edge cases: an odd number of lists passes the last one through unmerged (it pairs with None, and merge_two(l, None) returns l). Empty lists returns None immediately.

Comparison

Both approaches are O(n log K) - the right choice depends on the workload. For an interview, either is acceptable; the heap is more commonly expected because it generalizes to streaming and external sort.