Pointer surgery

Linked-list code fails at the first node, at the last node, and almost nowhere in between. The two failures have two causes. At the head there is no predecessor, so the line that deletes every other node, prev.next = cur.next, has no prev and needs a branch of its own. At the tail there is no successor, so a loop reading cur.next.val or fast.next.next without a guard dereferences None. A third bug is not positional at all — overwriting the only pointer to the rest of the list, which is what the reversal below turns on. Two habits remove most of those bugs: a dummy head, and drawing the arrows before writing the assignments.

The first element is the special case, so delete it

Removing a node needs prev.next = cur.next. Every node has a prev except the head, so the head needs its own branch — head = head.next — and now there are two code paths, one of them rarely exercised and easily wrong.

A dummy head is a node allocated in front of the real first element. It is never returned and never inspected; it exists so every real node has a predecessor.

def remove_all(head, target):
    dummy = ListNode(0, head)
    prev, cur = dummy, head
    while cur:
        if cur.val == target:
            prev.next = cur.next    # prev always exists now
        else:
            prev = cur
        cur = cur.next
    return dummy.next               # never `head`

Return dummy.next, not head. If the first node was the one removed, head still points at a node that is no longer in the list, and the caller gets it back. That single line is the most common defect in the pattern.

The same node builds lists. Merging two sorted lists, partitioning around a value, grouping in blocks of k: start with a dummy, append with tail.next = node then tail = node, return dummy.next. No "is this the first one?" branch anywhere in the loop.

Draw the arrows before you write the assignments

The second habit costs thirty seconds. Draw three boxes, the arrows that exist now, and the arrows you want after one step, then read the assignments off the drawing. Written the other way round you are debugging a picture you never made, which is why linked-list bugs feel untraceable. It is the same move as writing the brute force in the solving loop: make the state concrete before attacking it.

Reversal: three assignments, one legal order

One step of iterative linked-list reversal, and why nxt is saved before cur.next is overwritten100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 1 save the rest of the list
        cur.next = prev     # 2 flip this one link
        prev = cur          # 3 advance
        cur = nxt           # 4 advance
    return prev             # cur is None here; prev is the new head

Steps 1 and 2 cannot be swapped, and the failure is not a crash. Write cur.next = prev first, then nxt = cur.next, and on the first iteration nxt becomes None, because prev started as None. The loop exits and a list of five nodes comes back as a list of one: it runs, it returns something, and it is wrong.

Steps 3 and 4 cannot be swapped either: cur = nxt before prev = cur makes prev the node you were about to visit rather than the one you just flipped. And return prev, not cur — the loop ends when cur is None, so prev is sitting on the last node visited, which is the new head.

Fast and slow pointers

Two pointers over one list, one moving twice as fast, answer two different questions.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is now the middle node

After k iterations slow has moved k and fast has moved 2k, so when fast runs off the end at k ≈ n/2, slow is at index n//2. For even n that lands on the second of the two middles; if you need the first, loop on fast.next and fast.next.next instead. Say which one you are returning before you write it.

For cycles, the same pair gives the guarantee. If there is a cycle, fast enters it first and slow enters later. From that moment both are inside, and fast gains exactly one position per iteration. A gap that shrinks by exactly one cannot step over zero, so the pointers must land on the same node. That sentence is the proof, and it is what the question is testing. It also explains why a step of three is not a safe substitute: a gap shrinking by two can skip from 1 to −1 and orbit forever.

Finding the entry falls out of the arithmetic. Let L be the distance from head to entry, C the cycle length, a the distance from entry to meeting point. slow travelled L + a and fast travelled twice that, which is also L + a + kC, so L + a = kC and L = kC − a: head-to-entry equals meeting-point-forward-to-entry. Reset one pointer to the head, advance both one step at a time, and they meet there.

A visited-set solves the same problem in O(n) time and O(n) memory — at n = 100,000, roughly 100,000 × 60 bytes ≈ 6 MB of set. Two pointers cost sixteen bytes. Both are correct; only one answers "now do it in constant space".

The recursion trap at n = 100,000

Recursive reversal is four lines and it dies on the real constraint. CPython's default limit is 1,000 frames, so a list of 100,000 nodes raises RecursionError a hundredth of the way in. Raising the ceiling with sys.setrecursionlimit does not remove the problem; it makes the outcome interpreter-dependent. On CPython 3.10 and earlier every Python call also pushed a C stack frame, so a limit set past what the thread's 8 MB stack holds segfaults — no traceback, nothing to catch. From 3.11 a Python-to-Python call no longer touches the C stack and 3.12 turned over-deep C recursion into a RecursionError, so the same reversal may simply complete, still paying a heap frame per node. "It worked on my interpreter" is not a depth argument.

So the rule is a depth check, not a taste preference: recursion is fine at O(log n) depth — about 17 levels at n = 100,000 — and unsafe at O(n). That is the same constraint-first reading as complexity by counting.

One number worth carrying: each cur = cur.next is a dependent load from an address you only just learned, so nothing can prefetch it. That is a main-memory reference at ~100 ns against ~1 ns for a sequential array read: walking 100,000 scattered nodes costs on the order of 10 ms where scanning an array of 100,000 costs ~0.1 ms. Lists win on O(1) splice, not traversal — which is why the LRU cache in designing a data structure pairs one with a hash map instead of searching it.

In an interview

State the dummy head as a decision, out loud: "I will use a dummy head so the first element is not a special case, and return dummy.next." That sentence tells the interviewer you have met the bug before. Then draw the three-box picture and write the assignments off it rather than from memory.

The mistake that loses points is a recursive solution to a problem whose constraint says n = 100,000, with no mention of depth. It passes the small example, so the omission reads as not knowing the limit rather than as a shortcut.

Check yourself

You reverse a list and return cur instead of prev. What does the caller get?

None. The loop only exits when cur is None, so the function returns an empty list, and every element is still reachable — but only from prev, which you threw away.

Why does a fast pointer moving two steps at a time provably meet a slow pointer inside a cycle, but a pointer moving three steps does not?

Once both are in the cycle, a step of two closes the gap by exactly one per iteration, so the gap passes through every value down to zero. A step of three closes it by two, so an odd gap steps straight over zero and the two can circle forever without landing on the same node.

A list has 100,000 nodes and you have a clean four-line recursive reversal. What do you say, and what do you write?

Say that the recursion depth is O(n), which exceeds the default 1,000-frame limit, and that raising the limit only trades that for an interpreter gamble: CPython 3.10 and earlier segfault when the 8 MB C stack runs out, 3.11+ may survive but still pays a heap frame per node. Then write the iterative version with prev, cur and nxt, which uses O(1) space.