Merge K Sorted Lists

1. Problem & Core Objective

Given an array of k sorted linked lists, merge them into one sorted list and return its head.

lists = [[1,4,5], [1,3,4], [2,6]]
out   = [1,1,2,3,4,4,5,6]

Constraints: 0 <= k <= 10^4 · 0 <= list length <= 500 · total nodes N up to 10^4 × 500 in principle, and LeetCode bounds the sum at 10^4 · -10^4 <= Node.val <= 10^4

What's actually being tested: whether you notice that merging lists one at a time re-walks the accumulated result over and over. The fix — merge in pairs — is divide and conquer, and it's the same restructuring that turns O(n²) insertion sort into O(n log n) merge sort.

Let N = total nodes across all lists, k = number of lists.

2. First-Principles Thought Process

Start from what you have

Question 2 merges two sorted lists in O(n + m). The obvious extension: merge list 1 with list 2, then that result with list 3, and so on.

That's correct. It's also quadratic, and the reason is worth seeing precisely.

Why one-at-a-time is slow

Suppose all k lists have n nodes each, so N = kn.

• Merge 1 and 2: walk 2n nodes.
• Merge the result with 3: walk 3n.
• Merge with 4: walk 4n.
• …

Total: n(2 + 3 + 4 + … + k) ≈ n·k²/2 = O(N·k).

The accumulator gets re-walked on every single merge. The first list's nodes are copied k−1 times.

The fix: change the shape, not the merge

Merge lists in pairs: 1 with 2, 3 with 4, 5 with 6 — halving k each round. Then pair up the results, and again, until one remains.

Now count differently. In each round, every node is touched exactly once, so a round costs O(N). The number of rounds is how many times you can halve k: log k.

Total: O(N log k).

Same merges, same comparisons per merge — just reorganised so no node is walked more times than necessary.

The other route: a heap

Keep a min-heap of the current head of each list. Pop the smallest, append it, push its successor. Each of the N nodes enters and leaves the heap once, at O(log k) each: O(N log k).

Same bound, different mechanism. The heap is better when the lists arrive as a stream; divide and conquer is better when you have them all up front and want O(1) extra space.

3. Solution Paths

Approach 1 — Collect all values, sort, rebuild (brute force)

public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode l : lists)
        for (ListNode p = l; p != null; p = p.next) vals.add(p.val);
    Collections.sort(vals);

    ListNode dummy = new ListNode(), tail = dummy;
    for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; }
    return dummy.next;
}

• Time O(N log N) · Space O(N)

Counter-questions on this approach

⭐ "O(N log N) versus O(N log k) — how big is that difference really?"

k <= N, so log k <= log N and it's never worse. Concretely, with N = 10^4 spread over k = 100 lists, log N ≈ 13 and log k ≈ 7 — roughly twice the work. Not catastrophic.

The real objection is that it throws away the sortedness it was given. Each list is already ordered, so the next smallest element is always one of just k candidates — I never need a global sort. Discarding structure the input hands you is the mistake, not the constant factor.

"It also allocates N new nodes. Does that matter?"

Yes — O(N) space and it orphans the input nodes rather than splicing them. The merge-based approaches reuse every node and need O(1) extra space beyond recursion.

"Is there any case where this is the right answer?"

If the lists weren't sorted, absolutely — then there's no structure to exploit and sorting is optimal. Here the premise is handed to you.

Approach 2 — Merge one at a time (the natural but quadratic attempt)

public ListNode mergeKLists(ListNode[] lists) {
    ListNode result = null;
    for (ListNode l : lists) result = mergeTwo(result, l);
    return result;
}

• Time O(N·k) · Space O(1)

Counter-questions on this approach

⭐ "Each merge is optimal. Why is the whole thing not?"

Because the accumulator keeps growing and gets re-walked every time. By the final merge I'm walking N − n already-sorted nodes just to splice in the last list. The first list's nodes are traversed k−1 times in total.

The individual merges are optimal; the schedule is not. Summing 2n + 3n + … + kn gives O(nk²) = O(N·k).

⭐ "So how do you fix it without changing the merge at all?"

Merge in pairs. If I merge 1-with-2 and 3-with-4 simultaneously rather than sequentially, no node is ever in more than one merge per round, so a round costs exactly O(N). Halving k each round gives log k rounds and O(N log k) overall.

Same merge function, same total comparisons per round — I only changed the order in which merges happen. That's the whole insight.

"Would merging shortest-first help?"

It improves the constant but not the bound — it's essentially Huffman ordering, and it's still O(N·k) in the worst case where all lists are the same length. Pairing is the structural fix.

Approach 3 — Divide and conquer (optimal)

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    int interval = 1;
    while (interval < lists.length) {               // one pass per round
        for (int i = 0; i + interval < lists.length; i += interval * 2)
            lists[i] = mergeTwo(lists[i], lists[i + interval]);
        interval *= 2;
    }
    return lists[0];
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

Trace — 5 lists, indices 0–4:

3 rounds for 5 lists — ⌈log₂ 5⌉ ✓

• Time O(N log k) · Space O(1) — iterative, so no recursion stack

Counter-questions on this approach

⭐ "Walk me through the complexity. Why log k and not log N?"

Count by rounds rather than by merges. In any one round, the lists being merged are disjoint, so every node participates in at most one merge — a round costs O(N) total regardless of how the nodes are distributed.

Each round halves the number of live lists, so there are ⌈log₂ k⌉ rounds. O(N) per round times log k rounds is O(N log k). The k appears because it's the number of lists being collapsed, not the number of nodes.

⭐ "Why iterative rather than recursive divide and conquer?"

The recursive version reads more naturally, but it costs O(log k) stack. That's tiny — about 14 frames at k = 10^4 — so it's a fair choice. I write the iterative one because it's O(1) space with no real readability loss, and because the interval doubling makes the "rounds" structure, and therefore the log k, visible in the code.

"What does i + interval < lists.length guard against?"

An odd number of live lists. When one has no partner in a round it's simply left alone and carried into the next round — which is correct, since a single sorted list needs no merging. Without the guard you'd index past the end.

"You're overwriting the caller's array. Is that acceptable?"

It mutates lists in place, so I'd either document it or work on a copy. Given the merge already splices (and therefore consumes) the input lists, the array contents are meaningless afterwards anyway — but it's worth flagging rather than leaving implicit.

"Why <= in mergeTwo?"

Stability, exactly as in question 2 — on ties, take from the earlier list so equal elements keep their relative order.

Approach 4 — Min-heap of the k heads

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode l : lists) if (l != null) pq.offer(l);     // skip empty lists

    ListNode dummy = new ListNode(), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode smallest = pq.poll();
        tail.next = smallest;
        tail = tail.next;
        if (smallest.next != null) pq.offer(smallest.next);
    }
    return dummy.next;
}

• Time O(N log k) · Space O(k) for the heap

Counter-questions on this approach

⭐ "Same bound as divide and conquer. How do you choose between them?"

Space and availability. The heap is O(k); divide and conquer is O(1). But the heap only ever needs the current head of each list, so it works when the lists are streams you can't hold in memory or random-access — which is exactly the external multi-way merge used in database sorting.

With all k lists available up front, divide and conquer is the better fit. With k incoming streams, the heap is the only option.

⭐ "Why does the heap hold only k elements rather than all N?"

Because only the head of each list can be the next smallest — everything behind it is larger. So k candidates suffice, and I push a node's successor only when that node is removed. That keeps the heap at k and each operation at O(log k) rather than O(log N).

"(a, b) -> a.val - b.val — any problem with that?"

Subtraction can overflow. Here values are bounded by 10^4 so the difference fits easily, but as a habit Comparator.comparingInt(a -> a.val) is safer and states the intent directly. With values near Integer.MAX_VALUE, subtraction silently inverts the comparison. See 04.

"Why skip null lists when seeding?"

lists may contain empty lists (the constraint allows length 0), and offering null to a PriorityQueue throws NullPointerException. It's also why k in the complexity is really the number of non-empty lists.

Comparison

4. Why the Optimal Wins

Against sorting: the lists are already ordered, so the next element is one of k candidates, never N. Exploiting that replaces log N with log k.

Against one-at-a-time: this is the interesting comparison, because the merge function is identical. The only thing that changed is the schedule. Sequential merging re-walks the accumulator k times; pairwise merging touches each node once per round over log k rounds. O(N·k) → O(N log k) with no change to the inner loop.

That pattern — same work, better arrangement — is exactly what separates insertion sort from merge sort.

The framing worth keeping:

When combining k things pairwise, combine them in a balanced tree, not a chain. A chain re-walks the accumulator k times; a tree touches everything log k times.

5. Java Prerequisites

PriorityQueue is a min-heap by default

PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
pq.offer(node);       // O(log n)
pq.poll();            // O(log n) — removes and returns the smallest
pq.peek();            // O(1)

It permits duplicates but not nulls. See 14.

Comparator safety

(a, b) -> a.val - b.val                  // overflows for large values
Comparator.comparingInt(n -> n.val)      // safe and clearer

The doubling-interval loop — the iterative shape of divide and conquer:

for (int interval = 1; interval < n; interval *= 2)
    for (int i = 0; i + interval < n; i += interval * 2)
        arr[i] = combine(arr[i], arr[i + interval]);

Reuse mergeTwo from question 2 verbatim — don't rewrite it.

6. Interview Communication Guide

Clarifying questions: Can lists be empty, or contain null/empty lists (yes to all)? Reuse the existing nodes (yes)? Roughly how large are k and N (it decides heap vs divide and conquer)? Are the lists available up front or arriving as streams (the key design question)?

The pitch

"I already have a two-list merge that's O(n + m). The naive extension is to fold the lists in one at a time — but that's O(N·k), because the accumulated result gets re-walked on every merge. By the last one I'm traversing nearly all N nodes just to splice in the final list.

The fix isn't a better merge — it's a better schedule. Merge in pairs: 1 with 2, 3 with 4, and so on, halving the number of lists each round. Within a round the merges are disjoint, so every node is touched exactly once and a round costs O(N). There are log k rounds, so it's O(N log k).

The merge function is unchanged. I only reordered when the merges happen — same restructuring that separates insertion sort from merge sort.

I'd write it iteratively with a doubling interval, which keeps it O(1) space and makes the log k visible in the code.

The alternative is a min-heap of the k current heads: pop the smallest, append it, push its successor. Same O(N log k), but O(k) space. The heap only ever needs each list's head, so it's the right answer when the lists are streams you can't hold in memory — that's the external merge in database sorting. With all lists in hand, I'd take divide and conquer for the O(1) space."

Edge cases to volunteer:

Name [] and [null, null, [1]]. The first crashes anything that returns lists[0] without a length check; the second crashes a heap solution that seeds without a null filter.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the lists arrived as streams you can only read forward, one element at a time?"

Divide and conquer is out — it needs whole lists at once. The heap is exactly right: it only ever holds the current head of each stream, so memory is O(k) regardless of stream length. This is the external k-way merge that database sort-merge joins and LSM-tree compaction both use.

⭐ "What if k were enormous — say 10^6 lists of 2 nodes each?"

O(N log k) still holds, but the heap's O(k) space becomes 10^6 entries. Divide and conquer stays O(1) and wins. You could also merge in two stages — group the lists into batches, merge within batches, then merge the batch results — which bounds the heap size while keeping the tree shape.

"Merge k sorted arrays instead of lists."

Same two approaches. The heap version is identical with (arrayIndex, position) pairs instead of nodes. Divide and conquer needs O(N) scratch space for the merges, since arrays can't be spliced — that's the one place linked lists genuinely beat arrays.

"Return only the smallest m elements, not the full merge."

Use the heap and stop after m pops: O(k + m log k). Divide and conquer can't stop early — it has no notion of partial progress. This is where the heap is strictly better, and it's the shape of "k-th smallest in a sorted matrix".

"What if the lists were sorted descending?"

Flip the comparison — >= in the merge, or a max-heap via Comparator.reverseOrder(). Nothing structural changes; the algorithm needs consistent ordering, not a particular direction.

"Parallelise it."

Divide and conquer parallelises naturally: within a round, every merge is independent, so a round can be distributed across threads. That's O(N log k) work in O(log k) parallel rounds. The heap version is inherently sequential — each pop depends on the previous push — which is a strong argument for the tree shape at scale.