Week 3 · Linked List

Merge K Sorted Lists

Merge k sorted linked lists. The runner uses a list of sorted value lists.

Hard Linked List Week 3 Practice runner

Frame the problem

Each input list is sorted.
k may be zero and individual lists may be empty.
A heap or divide-and-conquer merge uses the sorted structure.

1. Reveal example inputs and outputs

Example 1

Input:

merge_k_lists([
  [
    1,
    4,
    5
  ],
  [
    1,
    3,
    4
  ],
  [
    2,
    6
  ]
])

Output:

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

Example 2

Input:

merge_k_lists([])

Output:

[]

2. Brute force first

Flattening and sorting works, but what information does it ignore?

3. Reveal the insight ladder

Seed a min-heap with the first value from each non-empty list.
Pop the smallest current value.
Push the next value from that same list.
Repeat until the heap is empty.

4. Dry run before code

[[1,4,5], [1,3,4], [2,6]].
Heap starts with 1, 1, 2.
Pop and replace from the same source list.
Output becomes [1,1,2,3,4,4,5,6].

5. Reveal final Python solution

import heapq

def merge_k_lists(lists):
    heap = []
    for list_index, values in enumerate(lists):
        if values:
            heapq.heappush(heap, (values[0], list_index, 0))
    result = []
    while heap:
        value, list_index, value_index = heapq.heappop(heap)
        result.append(value)
        next_index = value_index + 1
        if next_index < len(lists[list_index]):
            heapq.heappush(heap, (lists[list_index][next_index], list_index, next_index))
    return result

Complexity: Time O(n log k), space O(k) beyond output.

Interview narration

The heap holds the frontier from each list.
Each pop commits the globally smallest remaining value.
Pushing the successor preserves the frontier invariant.

Common traps

Pushing empty lists.
Forgetting tie-breakers for equal ListNode values in Python.
Flattening and sorting without discussing tradeoffs.

Follow-up drills

1. How does divide-and-conquer compare?

Pairwise merging is also O(n log k) and avoids heap tie-breaker details.

2. What heap tuple works for ListNode objects?

Use (node.val, unique_counter, node), because Python cannot compare ListNode objects when values tie.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.