Dummy head and splice

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The chain 1 → 2 → 3 → 4 → 5. Remove the 2nd box from the end, which is box 4. To cut a box out of a chain you need the box before it, so you can point its arrow past the one being removed: 3 → 5.

By hand you would count the chain (5 boxes), work out that the 2nd from the end is the 4th from the front, walk to the 3rd box, and splice. Two walks. Fine. Now try removing the 5th from the end: that is box 1, the head, and there is no box before it. You need a special rule: "if the box to remove is the head, just move the head". Every linked-list routine that deletes, inserts or merges grows a thicket of these "but what if it is the first box" cases, and each one is a chance for a bug.

The fix is a trick from carpentry: add a scrap piece in front of the real thing so the real first piece is no longer first.

Build the structure, one piece at a time

Piece 1: a dummy box. Create a box with no meaningful value and point it at the head: dummy → 1 → 2 → 3 → 4 → 5. Now every real box, including the old head, has a box before it.

Piece 2: two pointers a fixed distance apart. To find the box before the n-th from the end in one walk, start fast and slow both at the dummy. Move fast n + 1 = 3 steps ahead. Then move both one step at a time until fast runs off the end (null). The gap between them never changes, so when fast is one past the last box, slow is n + 1 boxes before that, which is the box just before the target.

slow is box 3, the box before box 4, which is the 2nd from the end.

Piece 3: splice. slow.next = slow.next.next, giving 1 → 2 → 3 → 5.

Piece 4: return dummy.next. That is the real head, whatever happened to the old one. If the target had been box 1, slow would have stopped at the dummy and the splice would have made dummy.next = 2, with no special case.

Why it is correct

The invariant: dummy.next is always the true head of the list being built or edited, and slow is always exactly n + 1 boxes behind fast.

The gap is set once and both pointers move together, so it never changes. When fast runs off the end (null), it is n + 1 past the last box, so slow is at position (last − n), the box just before the n-th from the end. Splicing there removes exactly the target. Because slow started at the dummy, the smallest position slow can reach is the dummy itself, which handles removing the head with the same line of code.

position(slow) = position(fast) − (n + 1); fast = null means slow = last − n

The same dummy serves any routine that builds a result chain: start with dummy, append boxes to a tail pointer, and return dummy.next. The "first box" case disappears because the dummy is always the first box.

Why it is fast

One walk over the chain: fast visits each box once.

time = O(n), extra memory = one dummy box + two pointers = O(1)

The counting method needs two walks; the dummy plus the fixed gap does it in one, and more importantly in one piece of code with no branches for the head.

How to recognise it in an interview

Reach for a dummy whenever a linked-list operation might change the head: "remove", "delete duplicates", "partition the list", "merge two lists", "add two numbers as lists". Say: "I put a dummy before the head so the head is not a special case, and return dummy.next at the end."

Remove Nth Node From End of List is the example above. Merge Two Sorted Lists appends to a tail that starts at the dummy, so the first appended box needs no special handling. Remove Linked List Elements walks with a prev pointer that starts at the dummy, so deleting a run of matching boxes at the front is the same loop as anywhere else.

02The idea in one line

A sentinel before head removes every 'is it the first node?' special case.

Reach for it when: Remove elements, delete duplicates, partition list, merge lists.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Remove Nth From End (n=2) on 1→2→3→4→5. These are its captions in order, so you can follow without the video or check a step you missed.

1. A dummy before head: deleting the first node is no longer a special case
2. Two pointers start at the dummy; move fast n + 1 = 3 steps ahead
3. fast → node 1 (step 1 of 3)
4. fast → node 2 (step 2 of 3)
5. fast → node 3 (step 3 of 3)
6. Advance both: slow → 1, fast → 4
7. Advance both: slow → 2, fast → 5
8. fast is at the tail, so slow is just before the node to remove
9. Splice: slow.next = slow.next.next, dropping 3
10. Return dummy.next: 1→2→3→5
11. One pass, no head special-case: O(n) time

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Linked List: Fast and slow pointers, In-place reversal, Digit-by-digit with carry, Clone with a map or interleaving.