Merge Two Sorted Lists

1. Problem & Core Objective

Given the heads of two sorted linked lists, splice them into one sorted list and return its head. The result should reuse the existing nodes.

list1 = 1 → 2 → 4
list2 = 1 → 3 → 4
out   = 1 → 1 → 2 → 3 → 4 → 4

Constraints: 0 <= n, m <= 50 · -100 <= Node.val <= 100 · both lists sorted ascending

What's actually being tested: the dummy head idiom, and whether you can splice nodes rather than copy values. This is the merge step of merge sort, and question 10 (Merge K Sorted Lists) is built directly on top of it.

2. First-Principles Thought Process

The greedy observation

Both lists are sorted, so the smallest remaining element overall is one of two candidates: list1's head or list2's head. Nothing deeper in either list can beat them.

So: compare the two heads, take the smaller, advance that list, repeat. That's the entire algorithm — there is no lookahead and no backtracking.

Why this is safe

Taking the smaller head can never be wrong. Everything behind it in its own list is larger (sorted), and everything in the other list is ≥ the other head, which is ≥ the one we took. So nothing that could have come earlier is left behind.

The annoying part: building the output

The logic above is trivial. The code gets ugly for a different reason — attaching the first node:

if (result == null) result = node;      // first node: set the head
else                tail.next = node;   // otherwise: append

That branch runs on every append and is pure noise.

The dummy head

Allocate one throwaway node and build behind it:

Now the list is never empty, so appending is unconditional. At the end, the real head is dummy.next.

This trick appears in almost every list-building problem. Question 6 (Add Two Numbers), question 10, question 11 — all of them use it.

3. Solution Paths

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

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode p = list1; p != null; p = p.next) vals.add(p.val);
    for (ListNode p = list2; 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+m) log(n+m)) · Space O(n+m)

Counter-questions on this approach

⭐ "You sorted data that was already sorted. What did that cost?"

A log factor I didn't need. The inputs are already ordered, and sorting throws that away and re-derives it. Merging two sorted sequences is O(n + m) — strictly linear — because at each step the next smallest is one of just two candidates. Sorting is the right tool only when you have no ordering to exploit.

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

It does. The problem says to splice the existing nodes, and allocating n + m fresh ones is O(n+m) extra space for no benefit. It also breaks any caller holding references into the original lists — their nodes are now orphaned rather than part of the result.

"When would this actually be reasonable?"

If the inputs weren't sorted, or if there were many lists with no ordering guarantee. Here both premises are handed to me, so declining to use them is the mistake.

Approach 2 — Two pointers with a dummy head (optimal)

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(), tail = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; }
        else                        { tail.next = list2; list2 = list2.next; }
        tail = tail.next;
    }
    tail.next = (list1 != null) ? list1 : list2;   // attach whatever remains, in one go
    return dummy.next;
}

Trace — [1,2,4] and [1,3,4]:

• Time O(n + m) · Space O(1)

Counter-questions on this approach

⭐ "Why <= and not <?"

Stability. On a tie, <= takes from list1 first, which preserves the relative order of equal elements across the two inputs. With < the result is still correctly sorted, so the tests pass either way — but if the nodes carried payloads beyond val, the ordering of equal keys would silently flip. It costs nothing to be stable, so I default to it.

⭐ "What does that last line before the return do, and why isn't it a loop?"

When one list runs out, the other is already sorted and every remaining element is ≥ everything emitted. So I can attach the whole remaining chain with a single pointer assignment instead of walking it node by node. That's the advantage of splicing over copying — the tail comes along for free.

"What if both lists are empty?"

dummy.next is never assigned in the loop, and the final line sets it to null since both are null. Returns null. No special case needed — again the dummy earning its place.

"Does this allocate anything?"

One dummy node, which is O(1) and discarded. Every node in the output is an original input node, re-linked. If even that allocation is unacceptable you can pick the smaller head as the start and merge into it, but the code gets noticeably worse for one node of savings.

"Are the input lists still valid afterwards?"

No — they've been consumed. Their nodes are now woven into the result, so walking the old list1 head yields a mixture of both. Worth stating: this mutates the inputs.

Approach 3 — Recursion

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

"The smaller head, followed by the merge of everything else."

• Time O(n + m) · Space O(n + m) stack

Counter-questions on this approach

⭐ "This is shorter and needs no dummy. Why not submit it?"

The stack. It recurses once per node, so n + m frames. At the stated limit of 50 nodes that's harmless, but this exact function is the merge step inside question 10 — where the lists can hold 10^4 nodes and the recursion would overflow. I'd rather write the version that scales.

"Why does the recursion not need a dummy head?"

Because it never appends — it returns the head of each merged suffix, and the caller attaches it. The dummy exists to solve "what do I attach the first node to", and recursion sidesteps that by building the list back-to-front as the stack unwinds.

"Is this tail recursive?"

No — the assignment list1.next = ... happens after the call returns. And it wouldn't help anyway, since the JVM doesn't eliminate tail calls.

Comparison

4. Why the Optimal Wins

Against sorting: the inputs are already ordered, and that ordering means the next element is always one of two candidates. Checking two things is O(1); sorting rediscovers a global order at O(N log N). Linear beats linearithmic, and more importantly it reflects understanding the input.

Against recursion: identical time, but O(1) space instead of O(N) stack — and this routine gets called on much longer lists in question 10.

The framing worth keeping:

When building a list, allocate a dummy head. The "is this the first node?" branch disappears, and so do the bugs that live in it.

5. Java Prerequisites

The dummy-head template — memorize this shape:

ListNode dummy = new ListNode(), tail = dummy;
while (...) {
    tail.next = someNode;
    tail = tail.next;
}
return dummy.next;

Splicing vs copying

tail.next = list1;             // splice: reuses the node, O(1), mutates the input
tail.next = new ListNode(v);   // copy:   allocates, leaves the input intact

Attaching a whole remainder

tail.next = (list1 != null) ? list1 : list2;

One assignment adopts an entire chain — only possible because you're splicing.

6. Interview Communication Guide

Clarifying questions: Both sorted ascending (yes)? Reuse the existing nodes or build new ones (reuse)? Can either list be empty (yes, both)? Do duplicates across lists need a particular relative order (ask — it motivates <=)?

The pitch

"Both lists are sorted, so the smallest element I haven't emitted yet is always one of two candidates — list1's head or list2's head. Nothing deeper can be smaller. So I compare the two heads, splice the smaller one on, advance that list, and repeat.

The logic is trivial; the awkward part is attaching the first node, which otherwise needs an 'is the result empty yet' branch on every append. I use a dummy head to kill that — build behind a throwaway node, return dummy.next.

I use <= rather than < so ties take from list1 first, which keeps the merge stable.

When one list runs out I attach the entire remainder with a single pointer assignment, since it's already sorted and everything in it is larger than what I've emitted. That's the payoff of splicing instead of copying values.

O(n + m) time — each node is visited once — and O(1) space beyond the dummy."

Edge cases to volunteer:

The disjoint-range case is worth naming — it's the one where the "attach the remainder wholesale" line does almost all the work, and it shows you understood why that line isn't a loop.

7. Follow-Up Questions — Modified Constraints

⭐ "Now merge k lists instead of two."

Question 10. Merging them one at a time re-walks the accumulator and costs O(k·N). Merging in pairs — k/2 merges, then k/4, and so on — gives O(N log k), because each node is copied once per round and there are log k rounds. A min-heap of the k heads gets the same bound.

"Merge them in descending order instead."

Flip the comparison to >=. Nothing else changes — the algorithm depends on the inputs being consistently ordered, not on the direction.

"What if the lists were doubly linked?"

Same merge, but each splice must also set the back-pointer: node.prev = tail. Easy to forget, and the resulting corruption only shows up when someone walks backwards.

"What if you could not modify the inputs?"

Allocate a new node per element: tail.next = new ListNode(smaller.val). Still O(n+m) time, but now O(n+m) space, and the remainder can no longer be attached in one assignment — you'd have to walk and copy it.

"What if the lists were enormous and stored on disk?"

This is exactly the external merge used in database sorting. Stream both inputs with buffered reads and write the output sequentially — the algorithm is unchanged, because it only ever needs the current head of each list. That's the real reason this pattern matters beyond interviews.

"What if one list is vastly longer than the other — a million against ten?"

Still O(n + m), dominated by the long list. But note the long list's tail is attached in O(1) once the short list is exhausted, so the real work is only about 2 × 10 comparisons plus the walk to wherever the short list runs out. Worth mentioning that the bound is loose here.