How do fast and slow pointers find the middle of a singly linked list in one pass?
answer
- two walkers, different speeds
- you never learn the length first
- one covers twice the ground
- after t steps: t nodes versus 2t
- leader exits at about t = n/2
basics
~20 sAdvance two references from the head at different speeds: slow moves one node per step, fast two. When fast runs off the end it has covered twice the distance, so slow is sitting at the middle. One sweep, constant extra memory.
solid answer
~40 sStart two references at the head. On every iteration `slow` follows one link and `fast` follows two, so after t iterations slow is t nodes in and fast is 2t nodes in — that ratio is the whole invariant. The loop stops the first time fast cannot take another double step, which happens after about n/2 iterations, leaving slow at the halfway node. You never learn or store the length, and you never allocate anything proportional to n: the cost is O(n) time and O(1) extra space. The loop guard has to test the fast reference itself *and* the link it is about to follow, otherwise the double hop reads past the end. On an empty chain the body never runs; on a one-node chain slow correctly stays put.
go deeper
Be ready to narrate the walk out loud: slow one link, fast two, stop when the fast one can go no further, answer is where slow stands. Say the costs — linear time, constant extra memory.
Explain the invariant rather than the code: after t iterations slow is t nodes in and fast is 2t, which forces slow to roughly half the length when the loop exits. Cover the empty and one-node cases without prompting.
Show judgment about when the idiom earns its place — a forward-only chain of unknown length where a second traversal is awkward — and admit that both approaches are linear rather than overselling the trick.
Own the readability call. On a chain you can freely walk twice, counting then walking is more obvious code; reserve the runner idiom for places where a single sweep genuinely matters, and make the choice explicit.
### Why the middle is not free on a chain A singly linked chain — picture a capture buffer where each packet record holds a link to the record captured after it — supports exactly one move: from a record, follow its link to the next one. There is no position arithmetic, so *jump to n/2* is not available, and in the usual framing you are not handed n either. The obvious plan is then two traversals: walk once counting records, then walk again and stop after half that many links. ### The runner idea Run two references over the same chain at different speeds from the same start. `slow` follows one link per iteration; `fast` follows two. The chain is finite, so `fast` reaches the end first, and it gets there having covered twice the ground `slow` has. Stop the instant `fast` can no longer take a double step and `slow` is standing at the halfway point. With both starting at the head: - after iteration 1: slow is 1 record in, fast is 2 records in - after iteration 2: slow 2, fast 4 - after iteration t: slow t, fast 2t That relation — the distance fast has covered is always twice the distance slow has covered — is the entire invariant. It holds trivially before the first iteration (0 and 0) and every iteration preserves it, because each iteration adds one to one distance and two to the other. ### Termination, and where slow actually lands The loop ends at the first t where fast cannot advance twice: either fast has already fallen off the end, or fast is sitting on the last record with nothing two hops away. For a chain of n = 2m + 1 records the loop runs m times and slow finishes on record m + 1 — the exact middle, with m records on each side. For n = 2m the loop also runs m times and slow finishes on record m + 1, which is the later of the two candidate middles. Counting from one, slow ends on record floor(n/2) + 1. Two boundary cases fall straight out of the same rule. On a one-record chain the body never runs, so slow stays on the only record — correct. On an empty chain there is nothing to return and the body must not run at all, which is exactly why the guard tests the fast reference before reading the link hanging off it. ### Cost, stated honestly Time is O(n). Fast follows about n links and slow about n/2, so the walk performs on the order of 1.5n link follows — the same order as counting and re-walking, which performs n plus n/2. The asymptotic class is identical, and it is worth being precise about that instead of claiming the runner version is *faster*. What it actually gives you is a single sweep from the head and no stored length. Space is O(1): two references, whether the chain holds ten records or ten million. Nothing proportional to n is allocated — no side collection of visited records, no copy of the chain. That is the property worth defending, because the beginner instinct — pour every record into an indexable container and take the element at half the size — is also O(n) time but O(n) memory. ### What the technique does not give you It does not give you random access; reaching the middle still costs a linear walk, so doing it inside a loop over every record is quadratic. It does not give you the record *before* the middle unless you carry a third reference trailing slow by one. It does not tell you n — if the caller needs the length as well, counting was going to happen anyway and the runner buys nothing. And it assumes a finite, forward-linked chain: the loop's exit condition is fast reaching the end. ### Generalising the runner Middle-finding is one instance of a family. Run two references over the chain holding a fixed relationship, and read the answer off the trailing one at the moment the leader hits the end. A speed ratio of two to one puts the trailer at the middle; a constant gap of k records puts the trailer k from the end. In both shapes the leader's arrival at the end is the signal and the trailer's position is the answer. ### Saying it in an interview Narrate the invariant rather than the code: two references, one twice as fast, stop when the fast one can go no further, answer is where the slow one stands — O(n) time, O(1) space, single sweep. Then volunteer the boundary behaviour (empty chain, one record, and which of the two middles you return on an even count) before being asked. That ordering is what separates a candidate who memorised the trick from one who understands why it terminates where it does.
- What does slow hold when the chain has exactly one node?It stays on that node, which is the right answer. The body never runs, because the fast reference cannot take two steps from a one-node chain, so slow never advances. An empty chain returns nothing at all — which is why the guard must test the fast reference itself before touching the link hanging off it.
- How would you get the node immediately before the middle instead of the middle itself?Carry a third reference that trails slow by one node, updating it just before each slow advance. That hands you the predecessor in the same single sweep and still constant space. The alternative — walking again from the head until the successor is the middle — costs a second traversal and buys nothing.
- Is the extra memory really constant when the chain holds millions of records?Yes. The walk holds two references and nothing else; their size does not depend on n. That is the difference from the naive fix of copying every record into an indexable container and taking the element halfway along, which is also linear time but adds linear memory and an allocation the chain did not need.
Two runners set off together on a one-way track, one at double pace. The moment the quick one crosses the finish line, the slower one is halfway.
saying these in an interview costs you the question
- Claims the length must be counted before the middle can be found
- Says the fast reference ends on the middle node
- Thinks the slow reference lands a quarter of the way in
- Assumes a side collection of every visited node is required
- Calls the one-pass walk asymptotically faster than counting