A singly linked structure need not end at null: a faulty link can lead back to an earlier node. A printing loop may then run forever. Floyd's slow-and-fast-pointer method detects a cycle using constant extra pointer storage and can locate its entry. The method applies to a finite, stable structure in which each node has one next pointer; it does not require the node values to be distinct. Compare node identities, not their stored values.
Cycle detection extends linked-list tracing.
Definition 2.2.1
(Tail length and cycle length)
Follow next from head. If the sequence reaches null, the structure is acyclic. Otherwise some node is visited twice. The entry is the first node that is visited twice. Let be the number of links from head to the entry (the tail length), and let be the number of nodes in the cycle that starts at the entry. The nodes reachable from head are then all distinct. The cycle problem takes head and returns a node of a cycle if one is reachable, and null if none is.
1. Safe detection before any proof
Assume that following next from head eventually reaches null or repeats a node. With the language's short-circuit and, the algorithm is:
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast: # compare node identities
return slow # a meeting node, not necessarily the entry
return null # no reachable cycle
The guard must check fast before accessing fast.next. The update is safe: when fast.next exists, fast.next.next is a valid pointer value even if it is null. On an acyclic path, slow trails fast and is non-null at that point; on a cyclic path neither pointer reaches null. If head is null, the loop does not execute. If a one-node list ends at null, it also does not execute. A self-loop instead produces a meeting on the first iteration. Checking equality only after moving prevents the initial equality slow == fast == head from falsely reporting a cycle in a nonempty acyclic list.
If the list reaches null, the fast pointer advances through at most its finite number of nodes and the guard eventually fails. No node can be visited twice on that path, so slow and fast cannot meet at a non-null node after positive unequal numbers of steps. If a cycle exists, both pointers eventually enter it; the next section shows why they must then meet.
Common mistake
(Comparing stored values instead of node identities)
Take the acyclic list of five nodes null with values . After the first iteration the pointers are at and , after the second at and . Both of those nodes hold the value , so a test on values would report a cycle in a list that has none. The identities and differ, so the identity test correctly continues, and the guard then stops the loop at null.
Common mistake
(Testing for a meeting before the first move)
If the equality test were placed before the pointers move, then for every nonempty list the test slow == fast would hold at the start, since both equal head, and every list would be reported cyclic. For the acyclic list null the correct loop makes one iteration, with slow at and fast at null, and returns null. This is why the first possible meeting time is , and why for the first meeting is at , not at .
2. Distances explain the meeting and entry
After loop iterations the slow pointer has taken links and the fast pointer . Once , both lie in the cycle. Relative to its entry, their positions are and modulo .
Concept lensGeometric
Chasing on a circle
Once both pointers are in the cycle, measure the gap as the number of links by which the fast pointer is ahead of the slow one, modulo . Each iteration the fast pointer moves two links and the slow pointer one, so the gap grows by exactly one. At iteration the gap is , and the pointers meet exactly when it returns to zero.
Theorem 2.2.2
(Detection and meeting time)
For a finite acyclic structure the loop ends with null. If a cycle is reachable, with tail length and cycle length , the loop returns a node on the cycle after exactly iterations, where is the least positive multiple of with . In particular , so detection takes time and pointer storage.
Proof
(The pointers coincide exactly at multiples of the cycle length)
Let . If , the slow pointer is still on the tail, at a node before the entry, and every node on the tail is distinct from every cycle node, so it cannot equal the fast pointer if that is in the cycle. If the fast pointer is also on the tail, it is links from head while the slow pointer is links away, and , so they are different nodes. Hence there is no meeting before .
For both pointers lie in the cycle, at positions and modulo relative to the entry. They coincide precisely when , that is,
There is a positive multiple of at or beyond , so detection terminates, and the first meeting time is the least such multiple. If it is , not zero, because the algorithm checks after moving. This multiple is at most : it equals when , and when the multiples of are spaced apart, so one of them lies in . So the work is , and only two pointers are stored.
Theorem 2.2.3
(Locating the entry)
Let the pointers meet after iterations, with . Leave one pointer at the meeting node and reset the other to head. If both advance one link per step, they first meet after exactly steps, and the node where they meet is the entry.
Proof
(The meeting node is steps before the entry in the cycle)
At the meeting the slow pointer has taken links, so the meeting node is at position relative to the entry. After further steps it is at position , the entry. The pointer reset to head reaches the entry after exactly links. So both are at the entry after steps.
They cannot meet earlier. Before steps the reset pointer is still outside the cycle, while the other pointer is always inside it, and a tail node differs from every cycle node. When , both already start at the entry and no extra move is needed.
Proof X-ray
Why the meeting node points to the entry
The proof rests on one quantity, the tail length . The condition comes from the meeting rule, and it turns the meeting position into modulo , a quantity that depends only on the tail length. That is what makes a second walk of steps from the meeting node land on the entry, and the same steps from head land there too. In the second phase the pointers must move at equal speed: otherwise the two walks would not both be links long at the moment of arrival. Uniqueness of the first meeting comes from the tail being outside the cycle. Note that the meeting node itself says nothing directly about the entry: only the pair of walks of equal length does, as the trace below shows.
3. A complete trace
Worked example 2.2.4
(A tail of two nodes and a cycle of four)
Let A → B → C → D → E → F → C. Here and . Record pointers after each detection iteration:
| Iteration | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | E |
| 3 | D | C |
| 4 | E | E |
The meeting is E, not C. Reset one pointer to A, leaving the other at E. After one step they are B,F; after two they are C,C, the entry. To measure the cycle length separately, keep one pointer at C and follow next until it returns to C, counting four links. It would be incorrect to infer just from an arbitrary meeting node's value or address.
Counterexample mode
The meeting node is the entry
A tempting claim is that the node where slow and fast meet is the first node of the cycle. In the trace above the meeting node is E, while the entry is C: two links later in the cycle. Indeed the meeting position is relative to the entry, which is nonzero because is not a multiple of . The claim holds only when divides , for example when . The repaired procedure resets one pointer to head and advances both pointers one link per step, and the second meeting is the entry.
Worked example 2.2.5
(A cycle that starts at the head)
Let A → B → C → A, so and . Starting with both pointers at A:
| Iteration | slow | fast |
|---|---|---|
| 1 | B | C |
| 2 | C | B |
| 3 | A | A |
The first meeting is at iteration , at the entry A; the iteration count is and not because equality is checked only after moving. Since , the pointers already agree on the entry and the reset phase needs no step. For the self-loop A → A the first iteration gives slow and fast both at A: the meeting is at .
Worked example 2.2.6
(Acyclic lists and the null guard)
For an empty list, head is null and the loop never starts, so null is returned. For A → null the guard fast.next != null fails at once and null is returned. For A → B → null the first iteration moves slow to B and fast to null; the comparison slow == fast is false (B is not null), and the guard then fails. For A → B → C → null, the first iteration gives B and C, and the guard fast.next != null fails at C. In every case the algorithm returns null without dereferencing a null pointer, because fast is tested before fast.next.
4. If the task asks to break the cycle
After locating the entry, start a pointer there and advance until its next points back to the entry. This node is the cycle predecessor; change only its next to null. For a self-loop the predecessor is the entry itself. All originally reachable nodes remain reachable exactly once, in their original first-visit order. This mutation is appropriate only when the caller owns the links and explicitly wants a linear list. The detection and entry routines themselves do not modify any links.
Checklist. State the finite/stable structure assumption and compare identities. Check null before dereference. Distinguish the meeting from the entry, justify the reset using modular positions, and count both the noncyclic prefix and the cycle when stating time. Do not claim that a single run proves behavior for a structure whose links change concurrently.
Exercises with solutions
Quick check
(Trace Floyd's detection on A → B → C → D → B. Give and , the meeting node, the iteration of the meeting, and the node found by the reset phase.)
Solution · Answer
The entry is B, so and (the cycle is B, C, D). The pointers after each iteration are: 1: slow B, fast C; 2: slow C, fast B; 3: slow D, fast D. They meet at D at iteration , the least positive multiple of that is at least . Reset one pointer to A and keep the other at D. After one step they are B and B, so the reset phase finds the entry B after step.
Quick check
(A list has tail length and cycle length . After how many iterations do the pointers meet, and at what position relative to the entry?)
Solution · Answer
The meeting iteration is the least positive multiple of that is at least , namely . The slow pointer has taken links, so it is node past the entry. This agrees with . The reset phase then needs exactly steps to reach the entry.
Quick check
(After Floyd's algorithm on A → B → C → D → B has found the entry B, how is the cycle broken so that the list becomes linear, and what is the result?)
Solution · Answer
Start a pointer at B and advance until its next is B. B.next is C, C.next is D, and D.next is B, so D is the cycle predecessor. Setting D.next to null gives the linear list A → B → C → D → null, in which all four nodes are still reachable exactly once.