Dummy Node & Pointer Rewiring

Linked list problems are rarely hard because of the algorithm. What trips people up is pointer management: keeping track of prev, curr and next without breaking the chain. Two habits make most of them routine. Put a dummy node in front of the head, and change pointers in an order that never loses the rest of the list.

The idea#

Deleting or inserting a node means changing the next of the node before it. The head has no node before it. So code that handles "delete a node" usually needs a separate branch for "delete the head". A dummy node removes that special case:

Create dummy = ListNode(0, head). Now every real node, the head included, has a predecessor.
Do all the work starting from dummy.
Return dummy.next. It is the new head, whatever happened to the old one.

With linked lists, always think of a dummy node. It costs one extra node and removes a whole class of bugs.

The second habit is about order. When you rewire, follow one rule: before you overwrite a next pointer, make sure something else still points to the node it pointed at. Save it in a variable or link it in first.

How to spot it#

These signals point to a dummy node.

The head itself might be deleted, moved or replaced.
"Remove all nodes with value val", "remove duplicates", "partition", "swap pairs".
You build a new list node by node. A dummy gives you a fixed place to start and a tail to append to.
There is more than one output list: split into two chains, then join them.

Template#

This is the delete-while-walking shape. prev moves forward only when you keep the current node.

dummy = new node whose next is head    # head gets a predecessor
prev = dummy
curr = head
while curr is not None:
    if curr should be removed:
        prev.next = curr.next          # unlink curr; prev stays put
    else:
        prev = curr                    # keep curr, so it becomes prev
    curr = curr.next
return dummy.next                      # the real head, even if it changed

The dummy helps when you build a new list, too. To build a list in order while you walk something else, use a dummy plus a tail pointer: tail.next = node, then tail = node.

Inserting right after the dummy builds a list in reverse order: node.next = dummy.next, then dummy.next = node. You get the reversal for free.

Rewiring in a safe order#

The template changes one pointer per step. Swaps and partial reversals change several at once, and that's where the rewiring rule from above matters most. Order the writes so no node becomes unreachable:

Point the node before the block at its new first node.
Let the node that will end up last grab the rest of the list.
Close the links inside the block.
Move prev to the new last node of the block.

Step 2 must come before any write that overwrites the only pointer to the rest of the list.

Pitfalls#

These mistakes break the chain most often.

Returning head instead of dummy.next. If the head was deleted, head points to a detached node.
Advancing prev after a deletion. When you unlink curr, prev stays where it is. The next node might need deleting too.
Overwriting next too early. Save curr.next (or link it elsewhere) before you change it.
Leaving a dangling tail. When you split or reorder nodes in place, set the last node's next to None. Otherwise it may still point into the old list and create a cycle.
Ignoring the constraints. Unusual constraints (unique values, a node that is never the tail) often allow a trick that the general case does not.

Worth exploring: in-place reversal (Reverse Linked List, LC 206). It is the prev / curr / next rewiring loop that Reverse Linked List II, Palindrome Linked List and Reorder List all build on.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Remove Linked List Elements

This is the template as written. The head itself may hold the value, so start from a dummy. Move prev only when you keep curr.

Hint: Remove Duplicates from Sorted List

Compare each node with the last node you kept. Give the dummy a value outside the allowed range (for example -101 when values are in [-100, 100]). Then the check curr.val == prev.val works from the very first node.

Hint: Delete Node in a Linked List

You get only the node to delete, so you cannot reach its predecessor. Copy the next node's value into this node, then unlink the next node. This works only because values are unique and the node is never the tail.

Hint: Swap Nodes in Pairs

Keep a prev before each pair first -> second. Set prev.next = second, then first.next = second.next, then second.next = first. If second.next is overwritten before first grabs it, the rest of the list is gone. After the swap, first is the new prev.

Hint: Partition List

Walk once and append each node to one of two chains, less and rest, each with its own dummy and tail. Link less_tail.next = rest_dummy.next at the end. If you reuse the original nodes, set rest_tail.next = None, or you may create a cycle.

Hint: Add Two Numbers II

The digits come most significant first, but addition starts from the least significant. Push both lists' values onto stacks, then pop and add with a carry. Insert each new digit right after the dummy, so the result comes out in the right order with no reversal step.

Hint: Reverse Linked List II

Use a dummy, because the reversed block may start at the head. Walk prev to the node just before position left. Then run the in-place reversal loop on the block and reconnect both ends.

Hint: Reverse Linked List

Walk with prev and curr. Save curr.next, point curr.next back at prev, then step both forward. When curr runs out, prev is the new head.

Hint: Add Two Numbers

The digits are stored least significant first, so add while you walk both lists, carrying as you go, and append to a dummy head. Keep going while either list or the carry remains.

Hint: Reverse Nodes in k-Group

Before reversing a group, check that k nodes remain. If not, leave them as they are. Reverse the k nodes in place, then connect the previous group's tail to the new group head. A dummy node keeps the first group from being a special case.

Key takeaways#

With linked lists, always think of a dummy node: the head gets a predecessor and dummy.next is the answer.
Change the predecessor's next to delete; advance prev only when you keep a node.
Save or relink next before you overwrite it.
A dummy plus a tail pointer is the standard way to build a list.
Inserting after the dummy builds a list in reverse for free.

Core idea#

Linked list problems are hard because of pointer management, not the algorithm. Put a dummy node before the head, and change pointers in an order that never loses the rest of the list.

Key points#

Delete or insert by changing the next of the node before it. The head has no node before it.
dummy = ListNode(0, head) gives every node a predecessor. Return dummy.next.
Before you overwrite a next pointer, make sure something else still points to the node it points at.
Build a list with a dummy plus a tail: tail.next = node; tail = node.
Insert after the dummy to build a list in reverse: node.next = dummy.next; dummy.next = node.
Spot it: the head may be deleted or replaced, "remove all", "partition", "swap pairs", or you build a new list.

Variations#

Problem	Trick
Swap Nodes in Pairs	`prev.next = second`, `first.next = second.next`, `second.next = first`, `prev = first`
Partition List	two dummy chains, then link `less_tail.next = rest_dummy.next`
Add Two Numbers II	two stacks, insert each digit after the dummy
Remove Duplicates	dummy with an out-of-range sentinel value
Delete Node (no head)	copy the next value, unlink the next node

Template#

dummy = new node whose next is head    # head gets a predecessor
prev = dummy
curr = head
while curr is not None:
    if curr should be removed:
        prev.next = curr.next          # unlink; prev stays
    else:
        prev = curr                    # keep curr
    curr = curr.next
return dummy.next                      # real head, even if it changed

Pitfalls#

Returning head instead of dummy.next. A deleted head is a detached node.
Advancing prev after a deletion. The next node may need deleting too.
Overwriting next too early. In a pair swap, set first.next before second.next.
A dangling tail. When you split or reorder in place, set the last next to None, or you can create a cycle.

Say it in an interview#

"A dummy node removes the head special case. The answer is dummy.next."
"Save next before you overwrite it."