Dummy Head Rewiring and Merging

Almost every bug in a linked-list problem lives at the head. Deleting the first node is different from deleting any other node. Building a list needs a special case for the very first element. Merging two lists needs to decide which head wins before the loop can even start.

The dummy head (or sentinel) makes all of that disappear:

Allocate one throwaway node that sits before the real list. Now every real node has a predecessor, so no operation is ever a special case. Return dummy.next at the end.

One extra node in exchange for deleting every if node is head branch you would otherwise write. It is the highest-leverage trick in this phase.

What you’ll learn

• Why dummy plus a tail pointer is the standard list builder.
• How a dummy makes head deletion identical to any other deletion.
• The prev/curr rewiring discipline, and the assignment-order rule that keeps you from losing the rest of the list.
• Where a dummy does not help.
• Three real LeetCode problems solved in the browser: 21, 2, 19.

Visual intuition

The dummy node exists to delete a branch. Watch the tail cursor: every append is tail.next = x with no “is the result empty yet?” test anywhere.

listWhy every list-building function starts with a dummyLC 21 · O(m + n)

remaininga:1a:3a:5b:2b:4b:6

1def merge(a, b):2    dummy = tail = ListNode(0)   # dummy avoids an empty-list special case3    while a and b:4        if a.val <= b.val:       # <= keeps the merge STABLE5            tail.next = a; a = a.next6        else:7            tail.next = b; b = b.next8        tail = tail.next9    tail.next = a or b           # attach whatever is left, in one line10    return dummy.next

a1,3,5b2,4,6

setupThe dummy node is the whole technique. Without it, the first append needs a special case ("is the result empty yet?"), and that branch is where linked-list code goes wrong. With it, "tail.next = x" is unconditionally correct, and the real head is just "dummy.next" at the end.

Play‹›1/8⟲

Note the final step: once one list is exhausted the other is attached whole, in one assignment, because it is already sorted. And note the comparison is <= rather than < — that is what makes the merge stable.

listA fixed gap between two pointers, in one passLC 19 · one pass

1def remove_nth_from_end(head, n):2    dummy = ListNode(0, head)     # so deleting the head needs no special case3    lead = lag = dummy4    for _ in range(n):            # open a gap of exactly n5        lead = lead.next6    while lead.next:              # walk both until lead hits the last node7        lead = lead.next8        lag = lag.next9    lag.next = lag.next.next      # lag is now just BEFORE the target10    return dummy.next

n2

setupA single pass, using a fixed gap between two pointers. The dummy matters here more than usual: if the node to remove *is* the head, lag needs somewhere to stand before it.

Play‹›1/9⟲

The gap is opened from the dummy, not the head. That is deliberate: it puts lag immediately BEFORE the target, which is the only position from which a node can be unlinked.

The cue

You are reaching for a dummy head when…

• You are building a new list node by node — 21, 2, 86, 725.
• You might delete or replace the head — 19, 82, 203, 237.
• You need a prev pointer for every node, including the first — 24, 82, 92.
• The problem splits one list into several — 86 Partition List, 328 Odd Even Linked List. Use one dummy per output list.
• You catch yourself writing if head is None or ... head ... more than once.

The anti-cue: if you are only traversing (counting, searching, finding a middle), a dummy buys you nothing. Reversal in place does not need one either — see In-place Linked List Reversal.

Template 1 — build a list

build_with_dummy.py

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next
 
 
def build(values):
    dummy = ListNode()          # throwaway node before the real head
    tail = dummy                # always points at the last real node so far
 
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next        # advance -- forgetting this is the classic bug
 
    return dummy.next           # the real head; dummy is discarded

The pair dummy + tail is the whole idiom. dummy never moves, so it still remembers where the list starts; tail walks forward as you append. Without the dummy, the first append needs if head is None: head = node and every later one needs tail.next = node — two cases instead of one.

Template 2 — merge two sorted lists

merge_two_lists.py

def merge_two_lists(a, b):
    dummy = ListNode()
    tail = dummy
 
    while a and b:
        if a.val <= b.val:              # <= keeps the merge stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
 
    tail.next = a or b                  # attach whatever remains, in one line
    return dummy.next

Two things worth noticing:

• tail.next = a or b replaces a second loop. At most one list is non-empty, and it is already sorted and already linked — so splice the whole remainder in $O(1)$ rather than copying node by node.
• Relinking, not copying. No new nodes are allocated, so this is $O(1)$ extra space.

Template 3 — delete a node, including the head

delete_with_dummy.py

def remove_all(head, target):
    dummy = ListNode(0, head)          # dummy points AT the real head
    prev, curr = dummy, head
 
    while curr:
        if curr.val == target:
            prev.next = curr.next      # unlink; prev stays put
        else:
            prev = curr                # only advance prev when we keep curr
        curr = curr.next
 
    return dummy.next

Only advance prev when you keep the node

This is the single most common rewiring bug. When you unlink curr, prev must stay where it is — it is now the predecessor of curr.next, and it may need to unlink that node too. Advancing prev unconditionally means consecutive matches are missed: remove_all([1,1,1], 1) would leave a 1 behind.

The rule: prev advances only in the else branch.

The assignment-order rule

When rewiring, you can destroy the pointer you still need. The safe habit is to save what you are about to overwrite before overwriting it:

swap_pairs_ordering.py

# LC 24 -- swap every two adjacent nodes
def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy
 
    while prev.next and prev.next.next:
        first = prev.next               # name the nodes BEFORE rewiring
        second = first.next
 
        first.next = second.next        # 1. first now points past second
        second.next = first             # 2. second points back at first
        prev.next = second              # 3. prev adopts the new front
 
        prev = first                    # first is now the tail of this pair
    return dummy.next

Naming the nodes first (first, second) and only then reassigning is what makes this readable and correct. Trying to do it with raw prev.next.next.next chains is how people lose ten minutes in an interview.

	Time	Space
Build / merge / delete with a dummy	$O(n)$	$O(1)$ — relinking, not copying

Dry run

Merge — a = 1→2→4, b = 1→3→4 (LC 21’s example). Each row is one iteration; a and b show where each cursor points afterwards.

step	comparison	taken from	tail now at	a head	b head
1	1 ≤ 1 ✓	a — <= keeps it stable	1 (a’s)	2	1
2	1 ≤ 2 ✗	b	1 (b’s)	2	3
3	2 ≤ 3 ✓	a	2	4	3
4	3 ≤ 4 ✗	b	3	4	4
5	4 ≤ 4 ✓	a	4 (a’s)	None	4
—	loop ends (a exhausted)	tail.next = a or b splices b’s remaining 4	—	—	—

Result 1→1→2→3→4→4.

• <= rather than < is what makes the merge stable. At steps 1 and 5 the values tie, and taking a first preserves the relative order of equal elements. That matters the moment nodes carry payloads beyond the sort key — and it is the same reason merge_sort uses <=.
• The half-built list temporarily trails into its source. After step 1, tail is a’s node 1, whose next still points at a’s own 2 — so walking dummy.next at that instant shows 1→2→4, not 1. Step 2 overwrites that pointer. Nothing is wrong; it is simply what relinking in place looks like mid-flight, and it is why printing the list inside the loop is a confusing way to debug this.
• tail.next = a or b is $O(1)$, not a second loop. At most one list is non-empty, it is already sorted and already linked, so one pointer assignment adopts the whole remainder.
• The dummy is what removes the special case. Without it, the first iteration would need to decide whether it is setting head or tail.next — a branch inside the hot loop, and the usual source of “works except on the first element”.

Deletion — remove_all([1,1,1], 1). Every node matches, including the head, which is exactly why the dummy exists.

curr	matches?	action	prev after
1st 1	✓	prev.next = curr.next — prev is the dummy, so the head is unlinked with no special case	dummy (stays)
2nd 1	✓	prev.next = curr.next again, from the same prev	dummy (stays)
3rd 1	✓	same	dummy (stays)

Result: empty list, dummy.next is None. Advance prev unconditionally and the result is [1] — the third node survives, because after unlinking the second, prev had already moved onto a node that is no longer in the list. On [1,2,6,3,4,5,6] with target 6 the same bug is invisible (the two 6s are not adjacent), which is why consecutive matches are the test case that must be in your head.

Complexity

Operation	Time	Space
Build a list with a dummy tail	$O(n)$	$O(1)$ extra — nodes are relinked, not copied
Merge two sorted lists	$O(n + m)$	$O(1)$
Delete all matching nodes	$O(n)$	$O(1)$
Merge k sorted lists, pairwise cascade	$O(nk)$	$O(1)$
Merge k sorted lists, divide and conquer	$O(n \log k)$	$O(\log k)$ recursion
Merge k sorted lists, min-heap of heads	$O(n \log k)$	$O(k)$

Two things worth being able to say:

• $O(1)$ space is the whole point of relinking. Building a new list by copying values is also $O(n)$ time but $O(n)$ space, and it hands the caller different node objects — which breaks any problem where node identity matters.
• The k-list bound is the interesting one. Merging list 1 into 2, then into 3, and so on, re-walks the accumulated prefix every time: $O(nk)$. Pairing them up instead — merge 1+2, 3+4, then the results — walks each element $\log k$ times, giving $O(n \log k)$. That is LC 23, and the heap formulation reaches the same bound with $O(k)$ space and no recursion.

The variant map

Variant	The dummy’s job	Canonical problem
Build an output list	dummy + tail appender	2 Add Two Numbers
Merge two sorted lists	Same, choosing the smaller head each step	21
Delete nodes	Gives the head a predecessor	19 · 82 · 203
Delete a whole run of duplicates	prev skips the entire run	82
Split into two lists	Two dummies, one per output	86 Partition List · 328
Swap or reverse in groups	prev anchors each group	24 · 25 · 92

Two dummies for a partition

LC 86 asks you to move every node less than x before the rest, preserving relative order. With two dummies it is almost trivial: build a less list and a greater list in one pass, then join them.

python

less_dummy, greater_dummy = ListNode(), ListNode()
less, greater = less_dummy, greater_dummy
while head:
    if head.val < x:
        less.next = head; less = less.next
    else:
        greater.next = head; greater = greater.next
    head = head.next
greater.next = None                  # ESSENTIAL: terminate, or you get a cycle
less.next = greater_dummy.next
return less_dummy.next

The greater.next = None is not optional. The last greater node still points into the middle of the original list, and forgetting to cut it creates a cycle — an infinite loop on the judge rather than a clean wrong answer.

Practice — real LeetCode problems

LC 21 — Merge Two Sorted Lists · Easy

Problem. Merge two sorted linked lists into one sorted list by splicing their nodes together. Return the head of the merged list.

Constraints. 0 <= len(each list) <= 50, -100 <= Node.val <= 100, both lists sorted ascending.

Examples. [1,2,4] + [1,3,4] gives [1,1,2,3,4,4] · [] + [] gives [] · [] + [0] gives [0]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Walk both lists, always attaching the smaller head. The dummy means you never have to decide which list provides the first node — the loop body handles it like any other step.

Time $O(n + m)$. Space $O(1)$ — nodes are relinked, not copied.

Two details:

• <= rather than <. With equal values, taking from list1 first makes the merge stable (equal elements keep their relative order across lists). It does not change the output for this problem, but it is the correct habit and it matters when nodes carry payloads.
• tail.next = list1 or list2. Python’s or returns the first truthy operand, so this attaches whichever list is non-empty, or None if both are. It replaces a whole second loop with one $O(1)$ splice.

Both-empty returning [] and one-empty returning the other are handled with no explicit guards, which is the dummy earning its keep.

Follow-ups you should expect: “Merge k lists (LC 23)?” — either merge pairwise in $O(n \log k)$, or use a heap of the current heads; see K-way Merge. “Do it recursively?” — merge(a, b) returns the smaller head with head.next = merge(rest, other); elegant but $O(n + m)$ stack space. “Merge descending?” — flip the comparison. “What if the inputs were unsorted?” — you would have to sort first; the merge itself relies on sortedness.

LC 2 — Add Two Numbers · Medium

Problem. Two non-empty linked lists represent non-negative integers with digits stored in reverse order, one digit per node. Add them and return the sum as a linked list in the same format.

Constraints. 1 <= len(each list) <= 100, 0 <= Node.val <= 9, no leading zeros except the number 0 itself.

Examples. [2,4,3] + [5,6,4] gives [7,0,8] (342 + 465 = 807) · [0] + [0] gives [0] · [9,9,9,9,9,9,9] + [9,9,9,9] gives [8,9,9,9,0,0,0,1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Reverse digit order is deliberate and helpful: the list heads are the least significant digits, which is exactly the order you add in by hand. Walk both lists together, carrying as you go.

Time $O(\max(n, m))$. Space $O(\max(n, m))$ for the output, which is required, so $O(1)$ auxiliary.

The load-bearing detail is or carry in the loop condition. Consider [5] + [5]: both lists are exhausted after one step but carry == 1, and the answer is [0, 1]. Without or carry, the loop ends and you return [0]. The [9,9,9,9,9,9,9] + [9,9,9,9] case is the same trap at scale — its answer is one digit longer than either input.

divmod(total, 10) returning (carry, digit) in one call is tidier than two separate // and % operations, and harder to get backwards.

Do not convert to an integer

It is tempting to walk both lists into Python ints, add them, and rebuild. It even works in Python, because integers are arbitrary precision.

But it defeats the purpose of the question, and it does not survive the follow-up: in a language with fixed-width integers, 100-digit numbers overflow. The digit-by-digit method is the answer that generalises, and an interviewer will usually say so.

Follow-ups you should expect: “What if the digits were in forward order (LC 445)?” — reverse both lists first, or use two stacks, or recurse to align the least significant digits. “Add three lists?” — the same loop with carry possibly exceeding 1, so divmod still handles it. “Subtract instead?” — borrowing, plus deciding which number is larger first.

LC 19 — Remove Nth Node From End of List · Medium

Problem. Given the head of a linked list, remove the nth node from the end and return the head. Try to do it in one pass.

Constraints. 1 <= list length <= 30, 1 <= n <= list length.

Examples. [1,2,3,4,5], n = 2 gives [1,2,3,5] · [1], n = 1 gives [] · [1,2], n = 1 gives [1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Open a gap of n nodes between two pointers, then slide both until the fast one reaches the last node. The slow pointer is then exactly n + 1 from the end — the predecessor of the node to remove, which is what you need in a singly linked list.

Time $O(L)$, one pass. Space $O(1)$.

The crucial choice is starting both pointers at dummy rather than at head. Landing on the predecessor is only possible because dummy gives the head one. ([1], 1) returning [] is the case that proves it: removing the only node means the head itself goes, and without a dummy you would need a separate if n == length: return head.next branch.

The loop condition while fast.next (not while fast) is what leaves fast on the final node rather than past it, keeping slow one before the target. Off-by-one here is the other common failure.

This is a fast-and-slow-pointer problem too — but note the pointers move at the same speed with a fixed gap, unlike cycle detection where they move at different speeds.

Follow-ups you should expect: “Two passes?” — count the length, then walk length - n steps; simpler to explain, and worth offering first if the one-pass version is not clicking. “What if n exceeded the length?” — the constraints forbid it, but you should say what you would do (validate and return head unchanged). “Remove the nth from the start?” — trivial with a dummy. “Remove all nodes with a given value (LC 203)?” — the delete template above.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 82 versus LC 83 — one word, a different problem

LC 83 keeps one copy of each value; the head always survives, so a dummy is optional. LC 82 removes every node that has a duplicate, so [1,1,2] becomes [2] — the head disappears. That makes the dummy mandatory, and the loop changes from “compare with the next node” to “skip the whole run”:

python

dummy = ListNode(0, head)
prev, curr = dummy, head
while curr:
    if curr.next and curr.val == curr.next.val:
        dup = curr.val
        while curr and curr.val == dup:      # skip the ENTIRE run
            curr = curr.next
        prev.next = curr                     # prev does NOT advance
    else:
        prev = curr
        curr = curr.next
return dummy.next

Being asked 83 and then 82 is a common escalation, and the dummy is the reason the second one stays short.

8 problems

2 easy6 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○21Merge Two Sorted Listseasy`dummy` + `tail`, then splice the remainder in one stepNeetCode 150Blind 75LeetCode Top Interview 150amazonmicrosoftapplebloomberg
• ○83Remove Duplicates from Sorted ListeasyKeep one of each run; no dummy strictly needed since the head survives
• ○2Add Two Numbersmedium`or carry` in the loop condition emits the final digitNeetCode 150LeetCode Top Interview 150
• ○19Remove Nth Node From End of ListmediumBoth pointers start at the dummy so head-removal is uniformNeetCode 150Blind 75LeetCode Top Interview 150
• ○24Swap Nodes in PairsmediumName the nodes before rewiring; `prev` anchors each pair
• ○61Rotate ListmediumFind the length, take `k % length`, then relink at the new breakLeetCode Top Interview 150
• ○82Remove Duplicates from Sorted List IImediumDelete **entire** runs -- the head can go, so a dummy is essentialLeetCode Top Interview 150
• ○86Partition Listmedium**Two** dummies; remember `greater.next = None` or you build a cycleLeetCode Top Interview 150

Interview follow-ups

They ask	What they’re checking	The answer
“Why a dummy node?”	Whether you can articulate it	It gives the head a predecessor, so insertion and deletion have no special case; you return dummy.next
“What’s the space complexity?”	Precision	$O(1)$ — one sentinel node, and existing nodes are relinked rather than copied
“Could you do it recursively?”	Flexibility	Usually yes, at $O(n)$ stack space; the iterative dummy version is $O(1)$
“Why <= and not < when merging?”	Care	It makes the merge stable, preserving relative order of equal elements
“How do you avoid losing the rest of the list?”	Method	Name the nodes you need in local variables before reassigning any next
“When does a dummy not help?”	Judgement	Pure traversal, and in-place reversal — there the head is expected to change and you already track prev
“How would you detect a bug like a cycle?”	Debugging instinct	Fast/slow pointers; and remember to terminate every list you split off

Edge-case checklist

• Empty list — head is None; the dummy makes most templates handle it for free.
• Single node — ([1], 1) for LC 19 returns []; the head-removal case.
• Removing the head — the whole reason for the dummy.
• Removing the tail — n = 1 in LC 19; check your loop leaves fast on the last node.
• Both lists empty (LC 21) — must return None, not a dangling dummy.
• One list empty — the tail.next = a or b splice covers it.
• Final carry (LC 2) — [5] + [5] gives [0,1]; the or carry condition.
• All nodes identical — [1,1,1] with the delete template; tests that prev does not advance on a match.
• Forgetting to terminate a split list (LC 86) — creates a cycle and hangs, rather than failing cleanly.
• Forgetting tail = tail.next — silently drops everything but the last appended node.

Self-check

pch.quizTag Dummy head and merging — self-check

1. What does the dummy node actually buy you?

   A It makes the list circular B It removes the head as a special case: `prev.next = …` works uniformly, including when the node being unlinked or prepended is the head itself C It stores the list length D It avoids null checks inside the loop body
   pch.quizShowAnswer

   B — It removes the head as a special case: `prev.next = …` works uniformly, including when the node being unlinked or prepended is the head itself — In remove_all([1,1,1], 1) every node matches including the head, and the dummy is what lets one line handle it. Returning `dummy.next` at the end is how the real head is recovered.

2. In the merge, why `if a.val <= b.val` rather than `<`?

   A To avoid an infinite loop on ties B Because `<=` takes from `a` on a tie, which keeps the merge stable — equal elements retain their original relative order C Because `<` would skip duplicates D They are equivalent for linked lists
   pch.quizShowAnswer

   B — Because `<=` takes from `a` on a tie, which keeps the merge stable — equal elements retain their original relative order — Stability only becomes visible when nodes carry payloads beyond the sort key, which is exactly when it matters. Same reason merge sort uses <=.

3. `tail.next = a or b` after the loop — what is it doing, and why is it not a second loop?

   A Copying the remaining nodes one at a time B Splicing whichever list still has nodes in O(1): at most one is non-empty, and it is already sorted and already linked, so one pointer assignment adopts the entire remainder C Setting the tail to null D Checking which list was longer
   pch.quizShowAnswer

   B — Splicing whichever list still has nodes in O(1): at most one is non-empty, and it is already sorted and already linked, so one pointer assignment adopts the entire remainder — This is the payoff of relinking rather than copying — the remainder needs no work at all, which is what keeps the merge O(1) in space.

4. In `remove_all`, when should `prev` advance?

   A On every iteration B Only when the current node is KEPT — after an unlink, `prev` is already the predecessor of the next node and may have to unlink that one too C Only after an unlink D Never; `prev` stays at the dummy
   pch.quizShowAnswer

   B — Only when the current node is KEPT — after an unlink, `prev` is already the predecessor of the next node and may have to unlink that one too — Advancing unconditionally turns [1,1,1] with target 1 into [1] — consecutive matches are missed. Non-adjacent duplicates hide the bug entirely, so that test case has to be deliberate.

5. Why walk `dummy.next` inside the merge loop and see the wrong list?

   A Because the dummy is not yet linked B Because the node just adopted still points at its own original successor until the next iteration overwrites that pointer — the half-built list temporarily trails into its source C Because the merge is not stable D Because tail lags one node behind
   pch.quizShowAnswer

   B — Because the node just adopted still points at its own original successor until the next iteration overwrites that pointer — the half-built list temporarily trails into its source — Nothing is broken; it is what in-place relinking looks like mid-flight. It is also why printing the list inside the loop is a misleading way to debug these problems.

6. Merging k sorted lists by folding each into an accumulator is O(nk). What gets you O(n log k)?

   A Sorting all the values first B Pairwise divide and conquer (merge 1+2, 3+4, then the results) or a min-heap of the k list heads — each element is then touched log k times instead of k C Merging from the longest list first D Nothing; O(nk) is optimal
   pch.quizShowAnswer

   B — Pairwise divide and conquer (merge 1+2, 3+4, then the results) or a min-heap of the k list heads — each element is then touched log k times instead of k — The accumulator version re-walks the growing prefix every round. This is LC 23, and the heap formulation reaches the same bound with O(k) space and no recursion.

Recall card

• Cue — building, merging, or deleting from a linked list where the head might change. If you are writing if not head or ... to special-case the first node, use a dummy instead.
• Do — dummy = ListNode(); tail = dummy, build with tail.next = node; tail = tail.next, and return dummy.next, never dummy.
• Delete — dummy = ListNode(0, head), then prev.next = curr.next on a match, and advance prev only when the node is kept.
• Merge — <= for stability; after the loop, tail.next = a or b splices the remainder in $O(1)$.
• Relink, never copy — $O(1)$ extra space, and node identity is preserved.
• Save before you overwrite when rewiring; a, b = b, a-style tuple assignment evaluates the right side first, which is what makes the one-liners safe.
• Cost — build/delete $O(n)$, merge $O(n+m)$, all $O(1)$ space. k lists: $O(n \log k)$ via pairing or a heap, not $O(nk)$ by folding.
• Test cases that catch the real bugs — deleting the head, deleting consecutive matches, one empty list, both empty.

Recap

• A dummy head gives the real head a predecessor, which deletes every is this the first node? special case. Return dummy.next.
• dummy + tail is the standard list builder; always advance tail.
• When merging, splice the remainder with tail.next = a or b instead of a second loop.
• When deleting, prev advances only when you keep a node — otherwise consecutive matches survive.
• Name the nodes before rewiring. The order of assignments is what makes or breaks pointer surgery.
• Two dummies to split a list — and terminate the second one, or you create a cycle.
• Everything here is $O(1)$ extra space, because you relink existing nodes rather than allocating new ones.

Next: Copy, Flatten and Reorder — the linked-list problems that need a hash map or a recursive descent rather than pure pointer work.