Linked Lists I — Traversal & Reversal

Review boundary and corrected contracts

These examples assume acyclic lists and ordinary truthy node objects with val and next attributes. Pointer rewiring preserves original node identities. Save cur.next before overwriting it. Merge assumes disjoint acyclic sorted lists; nth-from-end assumes 1 ≤ n ≤ length. A recursive reversal still uses O(length) call frames.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for linked lists is in the 6-month plan: S025 — theory.

Learning objective: Make the three-step reversal automatic and adopt the dummy head as a default, so that head-mutation and empty-list cases stop generating special-case code.

Series: LeetCode — From Basics to Production-Ready · Session 19 / 65 · Phase 1 · Core patterns

Why this session exists

The dummy head eliminates most linked-list edge cases. Use it by default and stop thinking about it.

Linked-list problems are rarely algorithmically hard. Nobody is asking you to invent anything — reversing a list, merging two sorted lists, deleting a node — these are operations a first-year student understands conceptually. What they test is whether you can execute pointer surgery without dropping anything, and specifically whether you can do it at the boundaries: empty list, single node, operation affecting the head itself.

Almost every bug in this category is a boundary bug. The middle of the list is easy; the ends are where people lose nodes. The dummy head is a two-line trick that makes the head stop being special, and it converts a category of problems from fiddly to mechanical.

The second half of the session is the reversal loop. It is four lines, you will use it in Reorder List, in Palindrome Linked List, in Reverse Nodes in k-Group, and in a dozen others. It must be muscle memory. If you have to derive it during an design review you have spent budget you needed elsewhere.

Blank-file warm-up

Five minutes, empty file, no notes. Write the reversal loop:

prev = None
while cur:
    nxt = cur.next
    cur.next = prev
    ...

Complete it, then write what the function returns and why it is not cur.

Then, separately, write a merge of two sorted lists using a dummy head, from scratch. If you find yourself writing if not head: return other special cases at the top, you have not internalised the dummy — that is today's finding.

Pattern anatomy

The shape that summons this pattern: you must relink nodes, and the operation can affect the first node.

Two tools, and the invariants that make them work.

For standalone practice, use this ordinary node type (no custom truthiness or equality):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

The reversal loop. Invariant: at the top of every iteration, everything from the original head up to but excluding cur has been reversed, and prev points at the head of that reversed portion.

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next        # 1. SAVE the rest before you destroy the link
        cur.next = prev       # 2. FLIP this node's pointer backward
        prev = cur            # 3. ADVANCE prev to the node just processed
        cur = nxt             # 4. ADVANCE cur to the saved next
    return prev               # cur is None here; prev is the new head

Four lines in a fixed order, and the order is not negotiable. Line 1 must come before line 2, because line 2 overwrites this traversal’s saved route to the rest of the list. Lines 3 and 4 must come after both, and in that order, because line 4 depends on nxt and line 3 must capture cur before it moves.

Return prev, not cur. When the loop exits, cur is None — it walked off the end. prev is the last node processed, which was the original tail, which is the new head. Returning cur returns an empty list, and it is the single most common slip on this function.

The dummy head. Invariant: dummy.next is always the true head of the result, and tail always points at the last node committed to the result.

def merge_two_lists(a, b):
    dummy = ListNode()          # sentinel; its value is never read
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b          # attach whichever still has nodes
    return dummy.next           # skip the sentinel

No emptiness checks anywhere. If both inputs are empty, the loop never runs, tail.next = None, and dummy.next is None — correct. If one is empty, the loop never runs and the other is attached wholesale — correct. The sentinel absorbs every boundary case because it guarantees there is always a node to attach to, even before the first real node exists.

tail.next = a or b uses Python truthiness: ordinary node objects with no false-returning __bool__ or zero-returning __len__ are truthy; None is falsy. It attaches the remaining list, or None when both are exhausted. If that is too clever for your taste, write the explicit if, but understand why the one-liner is correct.

Two-pointer with a gap. For "nth from the end", start both at a dummy and advance the lead pointer n steps. Then move both until the lead is on the final node; the trailing pointer is immediately before the target:

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)          # dummy so removing the head is not special
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:                   # stop with fast ON the last node
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next         # slow is the node BEFORE the target
    return dummy.next

The dummy is doing real work here. To delete node k you need a handle on node k − 1, and when k is the head there is no such node — unless a dummy provides one. Without it, removing the first element needs an entirely separate code path.

The cue

How you recognise this from the problem statement:

1. Any operation that can remove or replace the first node. Delete, insert-at-front, partition, remove-duplicates-including-the-first. Reach for the dummy before writing anything else.
2. "Reverse" in any form — whole list, sublist, in groups of k, alternating. The four-line loop is the atom in all of them.
3. "Nth from the end", "middle", "kth from last". Two pointers with a fixed gap, or slow and fast at different speeds. One pass, no length precomputation.
4. Merge, interleave, or zip two lists. Dummy head plus a tail pointer. This is also the merge step of merge sort on lists.
5. A stated constraint of O(1) extra space. That rules out copying to an array, which is otherwise the pragmatic answer to half these problems. When you see it, the problem wants pointer manipulation specifically.

The anti-cue: if you need random access by index, or you need to walk backward, a singly linked list is the wrong tool and the problem probably intends for you to say so. Converting to an array is a legitimate answer when no space constraint is stated — say what it costs and let a reviewer object if they want the pointer version.

Guided solve

Reverse Linked List. Given the head of a singly linked list, reverse it and return the new head.

The difficulty here is entirely about not losing the list. Each singly linked node has one successor field. Once you overwrite cur.next, this traversal loses its route to the suffix unless you saved it first; unrelated external aliases are not a substitute for maintaining the algorithm’s own references. Every correct solution is organised around that single fact.

Take 1 -> 2 -> 3 -> None.

Initial: prev = None, cur = 1.

Iteration 1: nxt = 2 (saved). 1.next = None — the list is now 1 -> None and separately 2 -> 3 -> None, held only by nxt. prev = 1, cur = 2.

Iteration 2: nxt = 3. 2.next = 1, so the reversed portion is 2 -> 1 -> None. prev = 2, cur = 3.

Iteration 3: nxt = None. 3.next = 2, giving 3 -> 2 -> 1 -> None. prev = 3, cur = None.

Loop exits. Return prev = 3. Head of 3 -> 2 -> 1 -> None. Correct.

Now check the boundaries without changing any code. Empty list: cur = None, loop body never executes, return prev = None. Correct. Single node: one iteration, nxt = None, 1.next = None, return prev = 1. Correct. No special cases needed — which is worth pointing out explicitly under a tight review, because it demonstrates you checked rather than hoped.

The recursive form exists and is worth being able to write, though I would not lead with it:

def reverse_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head      # the node after head now points BACK to head
    head.next = None           # head becomes the tail
    return new_head            # unchanged all the way up the stack

head.next.next = head is the whole thing, and it is genuinely hard to read. It says: my successor, which is now the tail of the already-reversed remainder, should point back at me. The recursion also costs O(n) stack, which fails the O(1) space constraint these problems usually state. Know it, but write the iterative version.

A trap specific to reversal: returning cur instead of prev. The loop exits precisely when cur becomes None, so returning it returns an empty list. It is a one-character mistake with a total failure, and it happens most often when someone reconstructs the loop from memory under time pressure rather than reasoning about the exit condition. The check takes two seconds — at loop exit, what is cur?

Solo timed

15 minutes each, timer visible.

• Merge Two Sorted Lists — dummy head plus a tail pointer; after the main loop, tail.next = a or b to attach whatever remains. Do not write emptiness checks at the top; verify afterward that the dummy handled them.
• Remove Nth Node From End of List — dummy, then advance fast exactly n steps, then move both until fast.next is None. Test with n equal to the list length, which is the case where the head itself is removed and where the dummy earns its place.

If you finish early: reverse the list, then reverse it again, and assert you got the original back. Any lost node shows up immediately.

Common failure modes

Overwriting cur.next before saving it. This traversal loses access to the unprocessed suffix. Save the successor first; external aliases might keep nodes alive, but cannot repair this loop’s missing reference.

Returning cur instead of prev from the reversal. Returns None. Total failure from one character.

Not using a dummy when the head can change. Forces a separate branch for head removal, and that branch is usually the untested one. Two lines of dummy replace ten lines of special case.

Losing the tail pointer's synchronisation. In merge, forgetting tail = tail.next after attaching means every subsequent attachment overwrites the previous one, so a processed prefix is lost; the exact remaining length depends on which suffix survives. For a=[1,3], b=[2,4], omitting the tail advance returns only [4].

Off-by-one in the gap advance. For nth-from-end, advancing fast by n from the dummy and looping while fast.next leaves slow on the node before the target. Advancing by n + 1 or looping while fast instead of fast.next shifts you one node and deletes the wrong element.

Creating a cycle. In problems where you reverse a portion and reattach, forgetting to terminate the old head (whole-list reversal) or reconnect it to the unreversed suffix (sublist reversal) can leave a link back into the reversed section. The symptom is an infinite loop on traversal, which in a submission looks like a timeout rather than a wrong answer.

Myth: A dummy head is a beginner's crutch — experienced programmers handle the head case directly and write tighter code.

Why: It is the opposite. The dummy exists to remove an entire class of boundary conditions, and removing boundary conditions is what experienced engineers do deliberately. Compare the two versions of remove-nth-from-end: with a dummy it is seven lines with no branches; without one it needs a separate path for 'the target is the head', which is the path least likely to be tested and most likely to be wrong. Two lines of sentinel is a strictly better trade than a branch you have to reason about every time.

Steps 1: Overwriting a node’s successor field removes this traversal’s route to the suffix unless another local reference preserves it.

Steps 2: Because the remainder must survive, any pointer flip must be preceded by saving the successor into a temporary — which fixes the four-line order and makes it non-negotiable.

Steps 3: Because the loop terminates when cur becomes None, the final value of prev is the last node visited, which was the original tail and is therefore the new head.

Steps 4: Because deleting or replacing node k requires a handle on node k-1, and the head has no predecessor, head-affecting operations require either a special case or a synthetic predecessor.

Steps 5: Because a dummy sentinel supplies exactly that synthetic predecessor, every node in the list including the original head gains a uniform predecessor, and the special case disappears entirely.

Steps 6: Testable prediction: the four-line reversal handles the empty list and the single-node list correctly with no added branches. If your version needs if not head: return None, it is doing redundant work — trace it on None and confirm.

Picture: A chain of paperclips you are re-hooking one link at a time. Before you unhook a clip from the one ahead, you keep a finger on the rest of the chain — otherwise it drops on the floor and is gone. The dummy head is a spare clip at the front so there is always something to hook the first real clip onto.

Trigger: Fires on any problem where nodes get relinked, and especially the instant you notice the operation might affect the first node.

Name: Iterative reversal with three pointers

Gain: O(1) extra space, no stack depth limit, handles empty and single-node input with no added branches, and is the version reviewers expect.

Cost: The four-line order is easy to scramble under pressure, and a single misordering silently loses the list.

Name: Recursive reversal

Gain: Shorter body, and it composes naturally with recursive tree and sublist problems where you are already recursing.

Cost: O(n) call frames, which violates an O(1)-auxiliary-space contract and can exceed the configured recursion limit. There is no portable safe node-count threshold; inspect sys.getrecursionlimit() and prefer iteration for potentially deep lists.

Name: Copy to an array, reverse, rebuild

Gain: Copying values into an array makes palindrome checking straightforward when O(n) space is allowed. For reversal, relinking an array of existing nodes preserves identities; rebuilding new nodes does not.

Cost: O(n) extra space, and it sidesteps the pointer manipulation the question was designed to probe.

Pick: Write the iterative version whenever the problem states O(1) space or list depth is not safely bounded below the configured recursion limit. Use the array copy only when no space constraint is given AND you say out loud that you are trading space for clarity — an unstated trade reads as not having noticed.

Complexity

Reverse Linked List — Time: O(n), Space: O(1). Each node is visited exactly once and its next pointer written exactly once. The only storage is three pointer variables, independent of list length. The recursive version is O(n) time but O(n) space from the call stack.

Merge Two Sorted Lists — Time: O(m + n), Space: O(1). At most m + n nodes are considered; when one list ends, the untouched remaining suffix is attached in one assignment rather than revisited node by node. No new nodes are allocated except the single sentinel, which is O(1) and discarded on return. Note this is genuinely O(1) auxiliary — the returned list reuses the input nodes rather than copying them, which is why the function mutates its arguments.

Remove Nth From End — Time: O(n), Space: O(1). The fast pointer traverses the whole list once; slow traverses at most all of it. Two passes' worth of work in one pass, which is the point of the gap technique — the naive version computes the length first and then walks again, and while that is also O(n), stating "one pass" is what the follow-up question asks for.

Self-check (answer follows each question).

Q: Why must you save cur.next into a temporary before setting cur.next = prev?

A: The traversal relies on cur.next to reach the unprocessed suffix. Save that reference before overwriting it; otherwise this algorithm loses its route to the remaining nodes. External aliases could still reference them, but the algorithm must not rely on those.

Q: Why does reverse_list return prev rather than cur?

A: The loop exits exactly when cur becomes None, having walked off the end. prev holds the last node processed, which was the original tail and is now the head of the reversed list.

Q: What specific problem does the dummy head solve, in one sentence?

A: Deleting or replacing node k requires a handle on node k-1, and the head has no predecessor; the dummy supplies a synthetic predecessor so every node including the head can be handled uniformly.

Q: In merge_two_lists, what does tail.next = a or b do and why is it correct when both lists are exhausted?

A: It attaches whichever list still has nodes, using Python truthiness. When both are exhausted both are None, None or None evaluates to None, and tail.next is correctly set to None to terminate the result.

Q: In remove_nth_from_end, why does the loop condition test fast.next rather than fast?

A: Stopping when fast.next is None leaves fast on the last node, which puts slow exactly on the node BEFORE the target — the handle needed to unlink it. Looping while fast leaves slow on the target itself, with no way back to its predecessor.

Q: Reverse Nodes in k-Group requires reversing each block of k nodes, leaving a trailing partial block untouched. Which pieces of this session compose to solve it, and what is the extra bookkeeping?

A: The four-line reversal applied to a bounded sublist, plus a dummy head, plus a group-before pointer. The extra work is checking that k nodes remain before reversing a block (walk ahead k steps, bail if you hit None), and after reversing, reconnecting the previous group's tail to the new block head and the new block tail to the next unprocessed node. The algorithm is unchanged; only the splicing bookkeeping is new.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Reverse Linked List enters today and should be re-tested more often than its difficulty suggests. It is a dependency of at least four later problems, and being slow on it is expensive out of proportion to its own value.

• Use a dummy head by default on any operation that can affect the first node. Two lines of sentinel beats a branch you have to reason about every time.

• The reversal is four lines in a fixed order: save next, flip pointer, advance prev, advance cur. Save first or you lose the list.

• Return prev, not cur. cur is None at loop exit — returning it returns an empty list.

• The iterative reversal handles empty and single-node input with no added branches. If you wrote a special case, you did not need it.

• Two pointers with a fixed gap answer 'nth from the end' in one pass with no length precomputation.

• In this merge loop, tail = tail.next after each attachment keeps the committed prefix; omitting it loses nodes, not necessarily leaving exactly two.

Corrective source notes

• Names and objects — Python 3.14 documentation — Multiple names can refer to the same object, so mutations and copied references must be distinguished. Checked 2026-10-07.

• Names and objects (CPython v3.14.0) — aliasing and mutations, freshly checked against tagged source on 2026-10-09.

• Recursion limits (CPython v3.14.0) — the configured limit is inspectable; raising it too far can crash the process. Rechecked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.