Why does a fast/slow middle loop test both fast and fast.next before every double hop?
answer
- two clauses, two different crashes
- the body reads two links, not one
- parity decides which clause saves you
- one covers empty and even counts
- short-circuit order is load-bearing
basics
~20 sEach clause prevents a different crash. Testing fast covers even-length chains, where fast has already run past the end; testing fast.next covers odd-length chains, where fast sits on the last node and the second hop has nowhere to go.
solid answer
~40 sThe double hop reads two links, so both have to exist before it runs. Drop the test on `fast` itself and the walk faults on every even-length chain — after the last iteration fast is nothing, and the next guard evaluation reads a link off nothing — plus on the empty chain. Drop the test on `fast.next` and it faults on every odd-length chain, including a single node: fast lands on the last node, its link is nothing, and the second hop dereferences that. The order matters too: the guard relies on left-to-right short-circuit evaluation, so `fast` must be tested before its link, otherwise the check itself performs the read it exists to prevent. Because each omission fails on one parity, a suite of only odd or only even cases passes a broken guard.
code
pseudocode · 15 lines// variant 1: the fast reference itself is never tested
slow = head
fast = head
while fast.next != NIL:
slow = slow.next
fast = fast.next.next
// survives odd counts; faults on even counts and on the empty chain
// variant 2: the link ahead of fast is never tested
slow = head
fast = head
while fast != NIL:
slow = slow.next
fast = fast.next.next // second hop from the last node
// survives even counts; faults on every odd count, including one nodego deeper
Know that the fast reference travels two links at a time and can jump straight past the end, so the loop has to check before each hop rather than after it.
Say exactly which input each clause saves you from: one covers the empty and even-length cases, the other the odd-length case where fast is standing on the last node.
Show the boundary tests that would have caught a dropped clause — zero, one, two and three nodes — instead of arguing about the guard in the abstract.
Own the defect class rather than the instance. Parity-dependent boundary bugs pass half a naive suite, so make boundary cases a review requirement instead of trusting a careful reading of the loop.
### What the guard is actually protecting The body of a middle-finding walk does one dangerous thing: it moves the fast reference two links at once. That single statement reads two links — the one hanging off fast, and the one hanging off the node that lands on. Both must exist at the moment of the read, and neither is guaranteed by the other. That is why the guard has two clauses and not one; each clause certifies one of the two reads. ### Which clause saves which input Take a capture chain of packet records and drop one clause at a time. **Guard is only `fast.next != NIL`** — the fast reference itself is never checked. On odd counts this happens to survive: with three records, fast goes 1 then 3, and record 3 has no link, so the loop exits cleanly with slow on record 2. On even counts it faults. With four records, fast goes 1, then 3, then falls off the end entirely; the next guard evaluation reads a link off nothing and the walk crashes. The empty chain crashes on the very first evaluation for the same reason. **Guard is only `fast != NIL`** — the link is never checked. Now even counts survive: with four records, fast goes 1, then 3, then off the end, and the guard catches that on the next evaluation. Odd counts fault. With three records fast reaches record 3, the guard sees a real node and admits the body, and the body then hops twice from the last record — the second hop reads a link off nothing. A single-record chain fails the same way on the first iteration. So the two clauses are not belt-and-braces duplication. They are parity-complementary: **one clause covers the even and empty cases, the other covers every odd case**, and the walk is only safe with both. ### Order is part of the correctness argument Writing the clauses in the other order does not merely look odd; it reintroduces the crash. Evaluating the link test first reads through a reference that may be nothing, which is precisely what the other clause exists to prevent. The guard is correct only because evaluation is left to right and stops as soon as the first clause is false. If you ever write this in a setting without short-circuiting, the two tests have to become nested conditionals instead. ### The testing lesson, which is the real point This is a parity-dependent boundary defect, and parity-dependent defects are the ones that slip through review. A routine with a dropped clause is not subtly wrong on rare data — it is completely correct on half of all inputs and crashes immediately on the other half. A suite built from three-node and five-node chains gives a broken guard a clean bill of health; so does a suite of two-node and four-node chains, for the opposite omission. The minimum useful set is four cases: zero, one, two and three nodes. Zero catches the missing reference test on an empty chain, one and three catch the missing link test, two catches the missing reference test on an even count. Everything larger is a repetition of one of those four. ### Where the guard is not enough The guard protects the loop, not the initialisation. A variant that starts fast one node ahead of slow reads the head's link before the loop begins, and no loop guard can save that on an empty chain — it needs its own check up front. Conversely, when both references start at the head, the guard's first clause doubles as the empty-chain check, and the routine has one special case fewer. That is a modest but real argument for that initialisation. ### How to answer it out loud Do not say *defensive programming*. Name the two reads the body performs, attach one clause to each, then give the parity: without the reference test it dies on even counts and on empty; without the link test it dies on odd counts including one node. Finish with the four boundary tests you would write. That answer demonstrates you can reason about a loop's preconditions rather than pattern-matching a memorised line.
- Does swapping the two clauses change anything?Yes, it breaks the walk. The guard is correct only because evaluation runs left to right and stops at the first false clause. Testing the link first reads through a reference that may be nothing — exactly the fault the other clause exists to prevent. The reference test has to come first.
- Which chain lengths does a suite need to catch a dropped clause?Zero, one, two and three nodes. Dropping the reference test faults on the empty chain and on even counts; dropping the link test faults on every odd count including a single node. A suite of only odd lengths, or only even ones, gives a broken guard a clean pass — which is how this defect reaches production.
- Does the guard change when fast starts one node ahead of slow?The loop guard is unchanged, but the initialisation now reads the head's link, so the empty chain must be rejected before the loop. The guard protects the walk; the initialisation decides which middle you land on and brings its own boundary case with it.
saying these in an interview costs you the question
- Calls the second clause redundant defensive coding
- Cannot say which input each clause prevents
- Reverses the clauses and assumes evaluation order is irrelevant
- Tests only odd-length chains and declares the loop safe
- Moves the check after the hop instead of before it