Coding Interview: How Do You Merge K Sorted Linked Lists?

Prompt and Applicable Context

Given an array lists containing the heads of k singly linked lists, merge every node into one list whose values are in non-decreasing order. Any input list may be empty, values may be negative or duplicated, and the total number of nodes across all inputs is N.

Assume each input is acyclic, already sorted, and shares no node with another input. The implementation may relink existing nodes and must not allocate a replacement node for every value. Equal values have no required order across different input lists. Return None when the array is empty or every head is None. Target O(N log k) time and O(k) auxiliary space.

Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

This is a linked-list problem, so pointer ownership is part of the contract. If the caller requires all input lists to remain unchanged, the algorithmic choice can stay the same, but the output must allocate N new nodes and its output space becomes O(N).

What the Interviewer Evaluates

The first signal is whether the candidate uses the sorted structure. Flattening all values and sorting them works, but spends O(N log N) time and O(N) additional storage. Scanning all current heads for every output node uses the sorted property but costs O(Nk). A strong answer asks what small set can contain the next global minimum.

The second signal is the frontier invariant. For every non-exhausted list, only its first unmerged node can be the next output. Every deeper node is at least as large because that list is sorted. A min-heap holding one frontier node per non-exhausted list therefore reduces a scan over up to k candidates to a minimum removal and insertion over a heap of size at most k.

The third signal is proof and accounting. The answer should state why the selected node is globally minimal, why pushing only its successor restores the invariant, why every node is emitted exactly once, and why the heap never exceeds the number of non-empty lists. Saying “use a priority queue” without that argument leaves the core reasoning unstated.

The fourth signal is implementation discipline. In Python, heap entries with equal numeric priorities must not fall through to comparing ListNode objects. A unique sequence number provides a tie-breaker. When nodes are reused, the code saves the original successor before detaching and appending the node, so the constructed prefix has one clear owner and does not retain a temporary pointer into an unmerged list.

The final signal is choosing between two optimal approaches. A min-heap and balanced pairwise merging both achieve O(N log k) time. The heap makes the frontier explicit and extends naturally to iterators or streams. Divide-and-conquer uses ordinary two-list merging and can use constant pointer workspace beyond the array of heads. The input contract decides which explanation is simpler.

Questions to Clarify Before Answering

• May I mutate and reuse input nodes? If yes, relink them and use only O(k) heap storage. If no,

allocate the output and report its O(N) space separately from auxiliary algorithm state.

• Are all inputs sorted and acyclic? The stated algorithm relies on both. Validating sortedness costs

O(N); detecting cycles also changes the work and should not be silently added to the base solution.

• What does k count? Let m be the number of non-empty lists. The heap holds at most m, so a more

precise bound is O(N log m) for m >= 2, with linear work for zero or one non-empty list.

• Must equal values preserve a cross-list order? The base question requires sorted values only. A

stable contract needs a defined source order encoded in the heap key.

• Can I use the language's priority queue? Usually yes unless the interviewer is separately testing

heap implementation. Clarify before spending interview time writing a binary heap from scratch.

• Are these fully materialized linked lists or lazy iterators? A heap handles both, but an iterator

version must avoid advancing a source until its current value is removed.

• What should happen to the input head array? The code below leaves the array entries untouched but

rewires their nodes. If the caller observes both, document that ownership transfer.

30-Second Answer Framework

“Only the first unmerged node of each sorted list can be the next global minimum, so I will keep those frontier nodes in a min-heap. I pop the smallest node, append it to the result, then push only its saved successor. The invariant is that the heap contains exactly one frontier from every non-exhausted list; therefore the popped node is safe, and restoring its source frontier preserves the invariant. Each of N nodes is popped once and at most one successor is pushed, with heap size at most k, giving O(N log k) time and O(k) auxiliary space. I will reuse nodes, add a unique tie-breaker so equal values never compare node objects, and test empty inputs, duplicates, negatives, uneven lengths, and one list. Balanced pairwise merging is the main alternative with the same time bound.”

Step-by-Step Deep Dive

Start with the straightforward alternatives and identify the repeated work:

Sequential merging is easy to underestimate. If k lists have similar length L, the work grows like 2L + 3L + ... + kL, which is O(Lk²). Since N = Lk, that is O(Nk). Pairwise merging avoids the unbalanced accumulator by combining lists in rounds, so every node participates in at most ceil(log₂ k) merge levels.

For the heap solution, maintain this invariant before every removal:

For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

Initialization inserts each non-empty head, so the invariant holds. Suppose it holds at the start of an iteration. Any unmerged node is either a frontier in the heap or appears after its list's frontier. Since each input is sorted, a deeper node cannot be smaller than that frontier. The minimum heap entry is therefore no larger than any unmerged node and can be appended safely.

After removing a node, only its source list loses its representative. Save that node's original successor, detach the node, append it, and insert the successor when it exists. All other source frontiers remain valid, so the invariant is restored. Each iteration emits one node; after exactly N iterations every list is exhausted and the heap is empty. This proves sortedness, completeness, and termination.

The following Python implementation uses a monotonically increasing sequence number as the second tuple field. That number is unique, so equal values never cause tuple comparison to reach the non-orderable node object.

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

There are m initial insertions, where m <= k is the number of non-empty lists. Every node is removed once, and every node except a final tail may cause one insertion. Heap operations cost O(log m) while the heap has at most m entries. For m >= 2, total time is O(N log m), conventionally stated as O(N log k); for m <= 1, the traversal is O(N). The heap, sequence counter, dummy, and pointers use O(m) auxiliary space. The returned nodes are the original nodes, so they are output rather than new algorithmic storage.

Detaching node.next is not needed to find the successor because it was saved first. It makes ownership explicit: the merged prefix never temporarily points into a source list that has not yet won the heap. The next append assigns the tail's successor. The algorithm never changes a value and never inserts the same node twice under the acyclic, disjoint-input contract.

Run tests that target structure, not only a happy-path array:

def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

For production-grade validation, also record the identities of all input nodes, walk the output with a visited set, and prove three properties: no cycle, exactly N unique node identities, and non-decreasing values. This catches duplicate insertion, node loss, and pointer cycles that a values-only assertion can miss.

Choose balanced pairwise merging when the interviewer wants pointer manipulation, a priority queue is unavailable, or minimizing heap storage matters. Choose the heap when sources are exposed as iterators, when the number of active sources changes, or when making the “next global candidate” mechanism explicit improves clarity. Both are valid optimal answers under the base contract; state the reason for the choice.

High-Quality Sample Answer

“I will reuse the input nodes and assume every list is sorted, acyclic, and disjoint. Let N be the total nodes and m the non-empty lists. The next output can only be one of the m current heads: any deeper node is at least as large as its head. I will therefore put one head per non-empty list in a min-heap.

My invariant is that the heap contains exactly the first unmerged node from every non-exhausted list and the output contains every popped node once in sorted order. I remove the minimum, save and detach its successor, append the node, and push that successor. The removed node is globally safe because every other unmerged node is behind a heap frontier that is no smaller. Pushing the successor restores the one- frontier-per-list invariant.

In Python, entries are (value, sequence, node). The unique sequence value prevents equal priorities from trying to compare node objects; it does not claim a cross-list stable order because the prompt does not require one. Each node is popped once and inserted at most once, with at most m heap entries. That is O(N log m), normally written O(N log k), and O(m) auxiliary space; zero or one non-empty list is linear.

I would test an empty array, all-empty lists, one list, unequal lengths, negatives, and equal values. I would also verify node identities and absence of cycles because the solution rewires pointers. Balanced pairwise merging is the main alternative: it also costs O(N log k) and uses only the two-list merge primitive, so I would prefer it if the exercise emphasizes pointer code or disallows a library heap.”

Common Mistakes

• Flatten and sort immediately → the solution ignores the sorted inputs and spends O(N log N) plus

output storage → Maintain one frontier per sorted source.

• Scan all k heads for every node → minimum selection becomes O(Nk) → **Use a size-k min-heap or

balanced pairwise merging.**

• Merge one list into a growing result repeatedly → early nodes are traversed across many later

merges → Combine lists in balanced rounds.

• Push every node into the heap → heap size grows to N, producing O(N log N) work → **Push only

one current node from each source.**

• Store (value, node) in a Python heap → equal values try to compare non-orderable node objects →

Add a unique numeric tie-breaker.

• Advance a source before saving its successor → pointer rewiring can lose the remaining list →

Save the successor first, then detach and append.

• Claim O(1) space because nodes are reused → the heap still holds up to k entries → **Separate

output allocation from auxiliary state.**

• Validate only output values → a cycle, duplicate node, or lost node can escape detection → **Check

node identities, count, order, and cycle freedom.**

• Add sorting and cycle validation without clarifying → the implementation solves a larger contract

and changes cost → State assumptions and add validation only when requested.

Follow-Up Questions and Responses

Why is the heap minimum the next global minimum?

Each non-exhausted sorted list contributes its first unmerged node. Any other node is behind one of these frontiers and cannot be smaller than it. Therefore the smallest frontier is no larger than every unmerged node. Removing it is safe, and inserting its successor restores coverage of that source.

What changes if equal values must be stable by input-list order?

Define stability precisely, then use a heap key such as value followed by source-list index. Because only one node per source is present, the source index resolves cross-list ties while each list's own order is preserved naturally. The base sequence tie-breaker guarantees comparability, not that stronger policy.

When is divide-and-conquer better than a heap?

Use balanced pairwise merging when the two-list merge is already available, the interview emphasizes pointer manipulation, or a priority queue is unavailable. Each round touches every remaining node once and there are O(log k) rounds. A heap is clearer for lazy sources and changing active-source counts.

What if the input lists must remain unchanged?

Keep the same selection logic but allocate a new node for each removed value. Time stays O(N log k). Auxiliary selection state remains O(k), while the required output allocation is O(N). State both instead of hiding output memory inside the space claim.

What if there are ten thousand list slots but only five are non-empty?

Initialization scans the k slots once, then the heap contains at most m = 5 entries. The precise time is O(k + N log m) and auxiliary space is O(m). Reporting only O(N log k) is safe as an upper bound but hides the benefit of skipping empty heads.

How would you merge sorted iterators instead of linked lists?

Read one value from each non-empty iterator into the heap together with its source identity. After yielding the minimum, advance only that source and insert its next value. The frontier proof is unchanged, the result can be lazy, and memory remains proportional to active sources rather than total values.

Can the code use heapreplace after removing a node with a successor?

Not after a separate heappop, because the old root has already left the heap. An implementation could peek, save the root source, and replace the root in one operation when that source has a successor, but the branch for an exhausted source remains. The simpler pop-then-push code is easier to prove in an interview and has the same asymptotic bound.

How would you test pointer correctness beyond examples?

Capture every input node identity before merging. Walk the result while rejecting repeated identities, count exactly N nodes, check every adjacent value, and confirm the identity set matches. Randomly generate sorted lists and compare values with a trusted flatten-and-sort oracle; the oracle verifies the test, not the production complexity.