skip to content

What breaks if you split a linked list for merge sort without severing the first half?

level: middleimportance: should knowfreq 46%

answer

  1. who still points at whom afterwards
  2. two head references, one chain
  3. a chain ends only where a link is null
  4. the recursion's input never gets smaller
  5. one write is the whole fix

basics

~20 s

Nothing is actually split. The first half's last node still links to the second half, so the first recursive call receives the whole list again, the subproblem never shrinks, and the recursion runs until the stack is exhausted.

solid answer

~50 s

Holding two head references does not create two lists — in a linked structure the boundary exists only where a link is cleared. If you locate the split point and pass `head` and `mid` down without writing null into the link before `mid`, the "first half" is still the entire chain: the recursion re-sorts the same input at every level and dies of stack exhaustion, or, with a sloppy base case, produces a result containing duplicated or cyclic sections. The fix is one write, and it dictates the traversal: you need a reference to the node *before* the split point, not just the split point itself, because a singly linked node offers no way back. Guard the base case too — a list of length 0 or 1 must return immediately, since any split that yields an empty half also fails to shrink the problem.

code

pseudocode · 10 lines
pseudocode
// BUG: this split does not split
sort(head):
    if head == null or head.next == null:
        return head
    mid = boundary_node(head)      // first node of the second half
    prev = node_before(mid)        // held, but never used
    first = head
    second = mid
    // missing: prev.next = null
    return merge(sort(first), sort(second))

go deeper

for a junior

Remember that a linked chain ends only where a link is null, so splitting means writing null into the node before the boundary — not just remembering two starting points.

for a middle

Explain why the omission overflows the stack: the first half is still the whole chain, so the subproblem never shrinks. Note that the fix requires holding the boundary node's predecessor.

for a senior

Diagnose from symptoms. A crash on every input of length two or more points at a structural split bug, not at data; duplicated or looping output points at halves that still overlap. Check the two-element case first.

for a principal

Push the invariant into the design: make the split routine return two chains it has already terminated, so no caller can forget the write, and require a length-two trace in review for any recursive routine over linked data.

## What a split actually is In an array, splitting is free and imaginary: you pass index ranges, and the halves exist because the callee agrees to stay inside its bounds. The data is untouched. A linked structure has no bounds to pass. A chain ends where a link is null and nowhere else, so a "half" is not a pair of endpoints — it is a chain that genuinely terminates. Two head references are just two entry points into one list. Splitting therefore requires a **write**: the node before the split point must have its link cleared, and that single write is what turns one chain into two. ## The failure, step by step Take a chronologically unsorted event log being sorted by a recursive list merge sort. Suppose the routine locates the split point (however it finds it), sets `first = head`, `second = mid`, and recurses on both without severing. - `second` is a genuine list — it inherits the original tail's terminating link, so it is the correct suffix. - `first` is *not* a list of half the length. Walking from `head` still passes through `mid` and continues to the original end. So the call on `first` receives the same input its parent received. Depth 1 sorts n elements, depth 2 sorts n elements, depth 3 sorts n elements. Nothing converges. The observable symptom is a stack overflow that appears on essentially every input of length two or more — not on some unlucky input, which is a useful diagnostic detail: a bug that fires universally is a structural bug, not a data-dependent one. If the base case is written loosely enough to stop the recursion anyway, the damage changes shape rather than disappearing: the merge is then handed overlapping chains, and nodes reachable from both cursors get relinked twice. The output contains repeated regions, or a node ends up pointing back into a part of the chain already emitted, and a later traversal spins forever. A merge sort that hangs on iteration rather than on recursion is usually this bug wearing a different hat. ## Why you need the predecessor Because the write is `prev.next = null`, the split routine must hold the node *before* the boundary. In a singly linked chain a node has no reference back, so if you only kept the split point you cannot terminate the first half without re-walking from the head to find its predecessor — an avoidable second pass. Whatever technique locates the boundary, arrange for it to leave a trailing reference one step behind. That is the practical reason interview answers keep a `prev` around, and forgetting it is the most common half-fix: candidates realize severing is needed, then discover they threw away the only reference that could do it. ## The base cases that must be right Termination needs both halves to be strictly smaller than the input: - Length 0 and length 1 are already sorted — return immediately. - Length 2 must split into 1 and 1. A boundary computation that returns the head itself gives an empty first half and a full second half, which never shrinks and overflows the stack just as reliably as forgetting to sever. So "does the split make progress on the smallest non-trivial input" is the single check that catches both the severance bug and the off-by-one boundary bug. Trace length 2 by hand before you trace anything else. ## Cost and the mirror image on the join side Severing costs exactly one write — O(1). Locating the boundary costs a traversal, O(n) at each level of the recursion, and that traversal is the price a linked structure charges for the free index arithmetic an array gives you. It does not change the overall order of growth, but it is the honest answer to "why is splitting not free here". There is a pleasing symmetry worth naming: the split spends one write to *break* a chain, and the merge spends one write to *splice* a chain back on when an input runs out. Both are O(1) because a link is the only thing that defines membership. Forget the first write and the recursion never shrinks; forget the second and the output is truncated. In both cases the bug is not arithmetic — it is having believed that pointing at something is the same as owning it.

  • Which reference must the split hold to sever the chain, and why?
    The node immediately before the boundary, because the write is `prev.next = null`. A singly linked node carries no reference backwards, so holding only the boundary node forces a second walk from the head to find its predecessor. Whatever locates the boundary should leave a trailing reference one step behind it.
  • The recursion terminates but the merged output contains repeated events. What happened?
    The halves overlapped. Unsevered or wrongly severed chains leave nodes reachable from both cursors, so the merge relinks the same nodes twice and emits regions more than once — sometimes producing a link back into an already-emitted section, which makes a later traversal spin. Trace a two-element input; the boundary or the severing write is wrong.

saying these in an interview costs you the question

  • Assumes two head references already mean two independent lists
  • Keeps the boundary node but not its predecessor
  • Blames the merge step for the stack overflow
  • Omits the single-node base case and recurses forever
  • Thinks severing requires a traversal rather than one write

context

resolving links…