Traversal & Pointer-Surgery Patterns

July 2026 · 21 min read

Once you can picture a node in memory, the next thing to internalise is that every linked-list algorithm — reversal, merge, cycle detection, LRU eviction — is the same tiny move repeated with different bookkeeping. Master that one move and its five loop shapes, and you stop memorising problems. You start deriving them. This post is the drill.

The One Rule: Save, Rewire, Advance

A pointer assignment is destructive. The instant you write p->next = something, whatever p->next held is gone unless you copied it somewhere first. That single fact generates the entire discipline of list surgery, which the series overview names in three beats:

• Save — before you overwrite a link, copy any pointer you still need into a local variable.
• Rewire — write the new links, in an order that never leaves a node stranded.
• Advance — move your cursors forward, using the pointers you saved.

Read-only traversal is just the degenerate case where the rewire beat is empty: you save nothing because you clobber nothing, and the whole loop collapses to advance. Insertion, deletion, reversal, and splicing all add a rewire beat between the save and the advance. When you feel lost inside a hard list problem, the fix is almost always to ask, in order: what am I about to overwrite, have I saved it, and am I advancing last?

The Five Canonical Templates

There are exactly five loop shapes worth committing to muscle memory. Each one is a named tool; you pick it by asking what you need to see at each step — the current node, the node before it, the link that reaches it, the node after it, or a second cursor somewhere else in the list.

1. Plain for-loop — read only

for (Node* p = head; p; p = p->next)
    process(p->val);

The condition p means p != nullptr. Reach for this whenever you only read: summing, printing, searching for a value, counting length, finding the maximum. No prev, no saving, because nothing is overwritten. It is O(n) time, O(1) space, and it is the only template where p = p->next living in the loop header is safe — the body never frees or relinks p.

2. The prev/cur pair — structural modification

Node* prev = nullptr;
Node* cur  = head;
while (cur) {
    if (shouldRemove(cur)) {
        Node* dead = cur;
        if (prev) prev->next = cur->next;   // splice out
        else      head       = cur->next;   // ... unless it is the head
        cur = cur->next;
        delete dead;
    } else {
        prev = cur;
        cur  = cur->next;
    }
}

The moment you must delete or insert, you need the node before the cursor, because a singly linked node cannot reach its own predecessor. Trailing prev one step behind cur solves that. The wart it carries is the if (prev) … else head = … branch: removing the head has no predecessor to rewire, so it becomes a special case you must never forget. The next template deletes that branch entirely.

3. Pointer-to-pointer — modification with zero special cases

This is the crown jewel, and it is worth deriving slowly rather than memorising. Why does the head need a special case at all? Because head is a Node* that lives in your function, while every other node is reached through some prev->next, which is also a Node* but lives inside a node. The prev/cur template treats those two as different things — hence the branch.

But they are the same type: both are “a Node* that currently points at the node I am examining.” So make the cursor a pointer to that link, whatever it is:

Node** pp = &head;          // pp aims at the link that reaches the current node
while (*pp) {
    Node* entry = *pp;      // the node that link points to
    if (shouldRemove(entry)) {
        *pp = entry->next;  // rewrite head OR prev->next -- uniformly
        delete entry;
    } else {
        pp = &entry->next;  // advance: aim pp at this node's own next-field
    }
}

Walk the two branches. *pp = entry->next writes through the handle: when pp == &head it updates head; when pp == &prev->next it updates that node's link. Same line, both cases, no branch. To advance without deleting, you re-aim the handle at the current node's own next field with pp = &entry->next. There is no head to special-case because the head is just the first link the loop ever looked at. When deletions can strike anywhere — including the first node — this is the template to reach for.

4. Lookahead — stop one short

for (Node* p = head; p && p->next; p = p->next) {
    if (p->val == p->next->val) { /* adjacent pair matches */ }
}

Use this when the body must look at p and its successor — comparing adjacent pairs, or stopping exactly on the last node so you can append. The condition p && p->next is what makes p->next->val safe to dereference: short-circuit evaluation checks p first, so on an empty list the second half is never touched. Removing duplicates from a sorted list is the canonical job for this shape, shown below.

5. Two-cursor / gap

Node* fast = head;
for (int i = 0; i < k && fast; ++i) fast = fast->next;  // open a gap of k
Node* slow = head;
while (fast) { fast = fast->next; slow = slow->next; }   // slide the gap to the end

Two cursors, either separated by a fixed gap or moving at different speeds, answer questions a single cursor cannot: “the n-th node from the end,” “the middle,” “is there a cycle.” The gap version above finds the k-th-from-last node in one pass. The different-speed variant — one hop versus two — is Floyd's tortoise and hare, which gets its own treatment in Fast & Slow Pointers.

Deleting While You Iterate

The single most common list crash is a use-after-free from deleting a node and then reading through it. Here is the bug in its natural habitat:

// WRONG: reads freed memory on the very next iteration.
for (Node* p = head; p; p = p->next) {
    if (bad(p)) delete p;   // p is now dangling...
}                            // ...and p = p->next dereferences it

After delete p, the object is gone, yet the loop header immediately evaluates p->next to advance. That read is undefined behaviour: it may return garbage, may segfault, or may appear to work until the allocator reuses the block. The fix is the save beat — capture the advance pointer before the node can die:

Node* p = head;
while (p) {
    Node* nx = p->next;   // SAVE first, while p is still alive
    if (bad(p)) {
        // ... unlink p from the list here ...
        delete p;         // REWIRE/free -- p is now invalid
    }
    p = nx;               // ADVANCE using the saved pointer, never p->next
}

This is save–rewire–advance with the ordering constraint made vivid: the advance pointer must be captured before the rewire destroys it. Notice the advance uses nx, never p->next, because after delete that field no longer exists.

Removing Every Occurrence of a Value

Putting the pointer-to-pointer template together with the save-before-delete rule gives the cleanest possible “remove all nodes equal to x”, with the head handled for free:

Node* removeAll(Node* head, int x) {
    Node** pp = &head;
    while (*pp) {
        Node* entry = *pp;
        if (entry->val == x) {
            *pp = entry->next;   // unlink (works even for the head)
            delete entry;        // safe: *pp already holds the successor
        } else {
            pp = &entry->next;
        }
    }
    return head;
}

The animation below runs the equally valid prev/cur form on six nodes so you can watch the two cursors move and the matching nodes get spliced out. Value 3 is the target; the survivors are 5 → 8 → 9.

Removing duplicates from a sorted list

When the list is sorted, equal values are adjacent, so the lookahead template fits perfectly. The subtlety is what happens after a deletion:

Node* dedupeSorted(Node* head) {
    Node* p = head;
    while (p && p->next) {
        if (p->val == p->next->val) {
            Node* dup = p->next;
            p->next = dup->next;   // splice out the duplicate
            delete dup;
            // do NOT advance: the new p->next may ALSO be a duplicate
        } else {
            p = p->next;          // only advance when no deletion happened
        }
    }
    return head;
}

Advancing after a delete would skip past a possible run of three or more equal values. The rule generalises: after you unlink a node, re-examine the same position; only advance when you leave a node in place. Both routines are O(n) time and O(1) extra space.

while (p) vs while (p && p->next)

These two conditions are not interchangeable, and picking the wrong one produces two opposite failures on two specific inputs.

• while (p) stops when p becomes null — it visits every node, including the last. If your body dereferences p->next->val, this condition lets it run on the final node, where p->next is null, and you crash. Breaks on: any list whose last node your body inspects a successor of.
• while (p && p->next) stops one node early, guaranteeing p->next exists inside the body. But it never runs the body with p on the last node, so if the last node needed processing on its own, you silently drop it. Breaks on: a one-node list when you expected the body to run at least once (it runs zero times).

And a subtle third case: writing while (p->next) with no null-check on p at all dereferences a null head immediately on an empty list. Always guard p itself before you reach through it.

Problem Phrasing → Template

Interview and contest prompts telegraph their template if you listen for the verb. This table is the mapping worth over-learning:

Check Yourself

Each situation names a task or a bug. Pick the statement that is actually true.

Practice

• LeetCode 203 — Remove Linked List Elements pointer-to-pointer the textbook use of the Node** template; the head can be removed.
• LeetCode 83 — Remove Duplicates from Sorted List lookahead classic p && p->next; do not advance after a delete.
• LeetCode 82 — Remove Duplicates from Sorted List II dummy head delete all copies of a duplicated value; a sentinel makes the head case vanish.
• LeetCode 237 — Delete Node in a Linked List copy trick no prev available, so copy the successor into the node and delete the successor.
• LeetCode 19 — Remove Nth Node From End of List two-cursor open a gap of n, then slide both to the end in one pass.
• LeetCode 876 — Middle of the Linked List fast/slow the different-speed cursor lands on the middle when fast reaches the end.