How do you detect whether a singly linked list has a cycle, and why does a plain walk hang?
answer
- a cycle removes what the walk relies on
- two walkers, different speeds
- what happens when one laps the other
- compare nodes, not their payloads
- no need to know the length first
basics
~20 sWalk two references, one hopping one node per step and one hopping two. If they meet, the list has a cycle; if the fast one runs off the end, it does not. A plain walk never reaches an end, so it spins forever.
solid answer
~50 sStart two references at the head; advance one by a single node per step and the other by two. If the list is acyclic, the fast reference reaches the end marker first and you report no cycle. If a link points back into the chain there is no end at all, so both references circle forever and the faster one eventually lands on the exact same node as the slower — that collision is the proof. Compare node **identity**, not stored payloads: two distinct records can legitimately hold the same value, so a repeated value proves nothing. The walk is `O(n)` time and `O(1)` extra space and needs no prior knowledge of the list's length. The alternative is to record every node you have already stepped on and stop at the first repeat, trading that constant space for `O(n)` memory.
go deeper
Recall the two-speed walk, that a collision means a cycle and running off the end means none, and that it costs no extra memory. Be able to say why a normal traversal never terminates on a cyclic chain.
Explain the mechanics: which reference decides termination, why the loop guard checks two links before the double hop, and why the comparison is node identity rather than payload equality.
Show you have diagnosed this in production — a job pinning a core and producing nothing — and that you know the constant-space walk is one option and remembering the traversed path is the other, with different diagnostic value.
Own the framing that detection is cheap and the real cost is choosing what the system does with a corrupted chain: memory ceilings on the workers that scan every chain, what the incident report must contain, and how the bad edit got written at all.
## What a cycle in a singly linked list actually is A singly linked list is a chain of nodes; each node holds a payload and one link to its successor, and the final node's link is an end-of-list marker. A **cycle** exists when some node's link points back at a node that is already on the chain. The resulting shape is usually drawn as the Greek letter rho: a straight **tail** of `L` nodes from the head to the first node of the loop (the *entry*), followed by a **loop** of `C` nodes that closes on itself. Two degenerate cases are worth naming up front: `L = 0`, where the head itself sits inside the loop, and `C = 1`, a single node linking to itself. The practical consequence is the one that gets you paged: **the end marker is gone**. Any code shaped "walk until the link is the end marker" — length counting, printing, serialising, a batch job that follows the chain record by record — never terminates. It does not crash and it does not slow down; it spins, pinning a core and producing nothing. That symptom is what detection exists to diagnose. ## The two-speed walk Start two references at the head. On each step, advance the first by one node and the second by two. - **If the list ends**, the fast reference reaches the end-of-list marker first and you report *no cycle*. It is the fast reference that decides termination, which is why the loop guard must check both that reference *and* its immediate successor before taking the double hop — the double hop dereferences two links, and either one can be the end. - **If there is a cycle**, neither reference ever finds an end. Both eventually enter the loop and circle it forever, and because the fast one gains ground on the slow one, it must eventually land on the *exact same node*. That collision is the proof of a cycle. The whole procedure needs no prior knowledge of the list's length, no modification of the nodes, and no auxiliary structure: **O(n) time, O(1) extra space**. ## Identity, not payload The comparison at the heart of the test is *are these two references looking at the same node*, not *do these two nodes hold the same value*. Distinct records routinely carry equal payloads — two approvals for the same amount, two events with the same code — and a repeated value proves nothing about the shape of the links. Conversely, a genuine cycle revisits the same node, whatever it contains. Candidates who compare payloads write a detector that reports phantom cycles on perfectly acyclic data. ## The other way: remember where you have been The obvious alternative is to walk once and record every node you step on in a set of already-seen node identities; the first node that is already in the set is a repeat, and a repeat means a cycle. It is easier to explain, it visits each node exactly once, and it gives you the whole traversed path for free. The price is **O(n) additional memory** that scales with the chain, and the set must key on node identity for exactly the reason above. Neither approach is universally right — the constant-space walk is the default when chains can be huge, and the remembered-path walk earns its memory when you need to report what you saw. ## What the answer must not claim - Not "count to the list's length and stop" — a cyclic list has no length to count to, and if you already knew the count you would not need to detect anything. - Not "the slow reference eventually returns to the head" — links only run forward; nothing sends a walk back to the head unless the head happens to be inside the loop. - Not "the collision node is where the loop begins" — the collision happens wherever the two references happen to coincide, generally somewhere past the entry. - Not "a cycle means some payload repeats" — see above. ## Sanity checks to state out loud An empty list and a single node with an end marker both terminate immediately on the guard. A single node linking to itself collides on the first step. A list whose head is the entry (`L = 0`) still works — the two references simply lap inside the loop from the beginning. Not one of these needs a special case in the code, which is part of why the technique is the standard answer.
- Why must the collision test compare node identity rather than the values stored in the nodes?Because payloads repeat legitimately. Two separate records can hold identical amounts, codes or names, so a repeated value says nothing about the link structure and would report phantom cycles on perfectly acyclic data. A cycle is defined by revisiting the same node, whatever it contains, so identity is the only sound comparison.
- If the list has no cycle, which reference ends the loop, and what must be checked before each double hop?The fast one, since it reaches the end first. Before the double hop you must check both that reference and its immediate successor, because the hop dereferences two links and either can be the end marker. Checking only the first is a boundary bug that fires exactly on acyclic input.
- Does the cycle have to include the head node for the technique to work?No. The general shape is a tail of some length leading into a loop, and the tail may be empty. If the head is already inside the loop the two references simply start lapping immediately and still collide. No special case is needed in the code for either shape.
saying these in an interview costs you the question
- Says a cycle means some stored value repeats
- Proposes counting to the list length to detect it
- Claims the slow reference eventually returns to the head
- Believes a plain traversal eventually reaches the end anyway
- Calls the collision node the start of the cycle