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.nextdummy.next at the end.

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

What you’ll learn

Why dummydummy plus a tailtail pointer is the standard list builder.
How a dummy makes head deletion identical to any other deletion.
The prevprev/currcurr 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.

The cue

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

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 dummydummy + tailtail is the whole idiom. dummydummy never moves, so it still remembers where the list starts; tailtail walks forward as you append. Without the dummy, the first append needs if head is None: head = nodeif head is None: head = node and every later one needs tail.next = nodetail.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

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 btail.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

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

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

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 (firstfirst, secondsecond) and only then reassigning is what makes this readable and correct. Trying to do it with raw prev.next.next.nextprev.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

The variant map

Variant	The dummy’s job	Canonical problem
Build an output list	`dummydummy` + `tailtail` 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	`prevprev` skips the entire run	82
Split into two lists	Two dummies, one per output	86 Partition List · 328
Swap or reverse in groups	`prevprev` anchors each group	24 · 25 · 92

LC 86 asks you to move every node less than xx before the rest, preserving relative order. With two dummies it is almost trivial: build a lessless list and a greatergreater 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

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 = Nonegreater.next = None is not optional. The last greatergreater 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) <= 500 <= len(each list) <= 50, -100 <= Node.val <= 100-100 <= Node.val <= 100, both lists sorted ascending.

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

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 list1list1 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 list2tail.next = list1 or list2. Python’s oror returns the first truthy operand, so this attaches whichever list is non-empty, or NoneNone 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 kk 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)merge(a, b) returns the smaller head with head.next = merge(rest, other)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) <= 1001 <= len(each list) <= 100, 0 <= Node.val <= 90 <= Node.val <= 9, no leading zeros except the number 00 itself.

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

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 carryor carry in the loop condition. Consider [5] + [5][5] + [5]: both lists are exhausted after one step but carry == 1carry == 1, and the answer is [0, 1][0, 1]. Without or carryor carry, the loop ends and you return [0][0]. The [9,9,9,9,9,9,9] + [9,9,9,9][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)divmod(total, 10) returning (carry, digit)(carry, digit) in one call is tidier than two separate //// and %% operations, and harder to get backwards.

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 carrycarry possibly exceeding 1, so divmoddivmod 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 nnth node from the end and return the head. Try to do it in one pass.

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

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

Editorial — approach, complexity, follow-ups

Open a gap of nn nodes between two pointers, then slide both until the fast one reaches the last node. The slow pointer is then exactly n + 1n + 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 dummydummy rather than at headhead. Landing on the predecessor is only possible because dummydummy gives the head one. ([1], 1)([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.nextif n == length: return head.next branch.

The loop condition while fast.nextwhile fast.next (not while fastwhile fast) is what leaves fastfast on the final node rather than past it, keeping slowslow 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 - nlength - n steps; simpler to explain, and worth offering first if the one-pass version is not clicking. “What if nn exceeded the length?” — the constraints forbid it, but you should say what you would do (validate and return headhead unchanged). “Remove the nnth from the start?” — trivial with a dummy. “Remove all nodes with a given value (LC 203)?” — the delete template above.

LeetCode problem set

#	Problem	Difficulty	The twist
21	Merge Two Sorted Lists	Easy	`dummydummy` + `tailtail`, then splice the remainder in one step
83	Remove Duplicates from Sorted List	Easy	Keep one of each run; no dummy strictly needed since the head survives
2	Add Two Numbers	Medium	`or carryor carry` in the loop condition emits the final digit
19	Remove Nth Node From End of List	Medium	Both pointers start at the dummy so head-removal is uniform
24	Swap Nodes in Pairs	Medium	Name the nodes before rewiring; `prevprev` anchors each pair
82	Remove Duplicates from Sorted List II	Medium	Delete entire runs — the head can go, so a dummy is essential
86	Partition List	Medium	Two dummies; remember `greater.next = Nonegreater.next = None` or you build a cycle
61	Rotate List	Medium	Find the length, take `k % lengthk % length`, then relink at the new break

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][1,1,2] becomes [2][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

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.

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.nextdummy.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 `nextnext`
“When does a dummy not help?”	Judgement	Pure traversal, and in-place reversal — there the head is expected to change and you already track `prevprev`
“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 Nonehead is None; the dummy makes most templates handle it for free.
Single node — ([1], 1)([1], 1) for LC 19 returns [][]; the head-removal case.
Removing the head — the whole reason for the dummy.
Removing the tail — n = 1n = 1 in LC 19; check your loop leaves fastfast on the last node.
Both lists empty (LC 21) — must return NoneNone, not a dangling dummy.
One list empty — the tail.next = a or btail.next = a or b splice covers it.
Final carry (LC 2) — [5] + [5][5] + [5] gives [0,1][0,1]; the or carryor carry condition.
All nodes identical — [1,1,1][1,1,1] with the delete template; tests that prevprev 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.nexttail = tail.next — silently drops everything but the last appended node.

Recap

A dummy head gives the real head a predecessor, which deletes every is this the first node?is this the first node? special case. Return dummy.nextdummy.next.
dummydummy + tailtail is the standard list builder; always advance tailtail.
When merging, splice the remainder with tail.next = a or btail.next = a or b instead of a second loop.
When deleting, prevprev 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Dummy Head Rewiring and Merging

What you’ll learn

The cue

Template 1 — build a list

Template 2 — merge two sorted lists

Template 3 — delete a node, including the head

The assignment-order rule

The variant map

Practice — real LeetCode problems

LC 21 — Merge Two Sorted Lists · Easy

LC 2 — Add Two Numbers · Medium

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

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?