Merge k Sorted Lists (LeetCode 23)

The problem

You get an array of k linked lists, each sorted in ascending order. Merge them all into one sorted linked list and return its head.

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

Every node from the three lists appears once, in sorted order.

How to think about it

Start with brute force. Pour every value into one array, sort it, and build a new list: O(N log N) for N total nodes, plus O(N) extra memory. It works, but it throws away the fact that each list is already sorted.

A better baseline: merge two at a time. Merging two sorted lists is a classic O(a + b) job. Merging list 1 with list 2, then the result with list 3, and so on, makes the early nodes get copied over and over: O(N·k). Pairing lists up like merge sort (1 with 2, 3 with 4, then the results) brings that down to O(N log k).

The key insight: at any moment, the next node is one of k candidates. The smallest unmerged node must be the head of one of the lists. So keep the k current heads in a min-heap. Pop the smallest, attach it to the output, and push that node’s successor. Each step is O(log k), and every node passes through the heap once.

Which pattern is this? Heaps, as a k-way merge. The tell is “k sorted inputs, produce one sorted output”. It’s the lesson’s main worked example and the base of many other heap problems.

Approach

1. Push (head.val, i, head) for each non-empty list i.
2. Create a dummy node and a tail pointer.
3. While the heap isn’t empty, pop the smallest (val, i, node), attach node after tail, and move tail forward.
4. If node.next exists, push (node.next.val, i, node.next).
5. Return dummy.next.

The list index i sits in the tuple to break ties. Without it, two equal values would make Python compare ListNode objects, which raises a TypeError.

Solution

import heapq
def merge_k_lists(lists):
    h = []
    for i, l in enumerate(lists):
        if l: heapq.heappush(h, (l.val, i, l))               # i breaks ties so nodes are never compared
    d = ListNode(); tail = d                                 # dummy head
    while h:
        val, i, node = heapq.heappop(h)                      # smallest current head
        tail.next = node; tail = node
        if node.next: heapq.heappush(h, (node.next.val, i, node.next))   # its successor joins the race
    return d.next
# merge_k_lists([[1,4,5],[1,3,4],[2,6]]) -> [1,1,2,3,4,4,5,6]

Dry run

On the example (lists 0, 1, 2). The heap starts with heads 1 (list 0), 1 (list 1) and 2 (list 2). Heap entries are shown as (value, list):

The pops, in order, are 1, 1, 2, 3, 4, 4, 5, 6: the merged list.

Complexity

• Time: O(N log k) for N total nodes. Each node is pushed and popped once, and the heap holds at most k entries.
• Space: O(k) for the heap. The output reuses the existing nodes, so no new list is built.

Edge cases and pitfalls

• Empty input [] returns None.
• Some or all lists empty, like [None, None]: the if l check skips them, and the result is None.
• Ties between equal values crash without the index in the tuple. This is the bug interviewers watch for in Python.
• Sequential pairwise merging looks fine for small k but is O(N·k). Mention the heap or divide-and-conquer merge.
• One list is returned as-is, after passing through the heap.

Related problems

• Merge Two Sorted Lists (LeetCode 21): the two-list building block.
• Find K Pairs with Smallest Sums (LeetCode 373): the same k-way merge over rows of a sum grid.
• Kth Largest Element in an Array (LeetCode 215): the other core heap pattern, top-K.