How to Learn Cycle-Finding Algorithms: Floyd’s Tortoise–Hare, Brent’s Method, Functional Graphs and Constant Memory

Wait, What?

Two pointers moving at different speeds can discover a loop without remembering where they have been.

Cycle finding is a compact algorithmic idea with unusually deep reach. The beginner version appears in linked lists: does following next eventually repeat a node? The more general version appears whenever a deterministic function repeatedly maps one state to the next. Because each state has one successor, the reachable structure must eventually end or repeat. In a finite state space with no terminating state, repetition is inevitable.

Floyd’s tortoise-and-hare algorithm detects a cycle with constant extra memory. Brent’s algorithm solves the same general problem with a different stepping strategy and can reduce expensive successor-function evaluations. Learning both gives students a valuable lesson: the same mathematical invariant can support more than one implementation strategy.

Quick Read

Functional graph: every state has at most one chosen successor under the function being iterated.
Tail length μ: number of steps before entering the cycle.
Cycle length λ: number of distinct states in the repeating loop.
Floyd: move one pointer one step and another two steps until they meet.
Second phase: reset one pointer to the start and move both one step at a time to find the cycle entry.
Brent: uses expanding power-of-two blocks and often fewer successor evaluations.
Space: O(1) extra memory when state comparison and successor evaluation are constant-space operations.

1. Start With a Sequence, Not a Linked List

Let a deterministic function f generate a sequence:

x₀, x₁=f(x₀), x₂=f(x₁), …

If the reachable state space is finite, some state must eventually repeat. From the first repeated state onward, the future repeats forever because the successor function is deterministic. The shape is therefore a tail leading into a cycle: the Greek letter μ is commonly used for the tail length, and λ for the cycle length.

A linked list with a loop is just one concrete instance. The successor function is node.next.

2. Why a Visited Set Is the Obvious Baseline

The simplest correct method stores every visited state in a hash set. Before processing the next state, check whether it has appeared before. The first repeat proves a cycle.

This is a good baseline because it makes the information problem explicit: if you remember the whole past, repetition is easy to detect. Floyd’s algorithm is interesting because it throws away almost all that memory and still succeeds.

3. Floyd Phase One: Make the Pointers Collide

Initialize two pointers from the start. The tortoise advances one successor per iteration. The hare advances two. If the structure terminates before the hare can continue, there is no cycle in a linked-list setting. If a cycle exists, both pointers eventually enter it.

Once both are inside the cycle, look only at their positions modulo λ. The hare gains one cycle position on the tortoise each iteration because it moves two steps while the tortoise moves one. Eventually that relative offset becomes zero modulo λ, so they meet.

4. “The Faster Pointer Will Catch It” Is Not Yet a Proof

A visual track analogy is helpful, but professionals need the modular argument. Suppose the tortoise is at cycle position a and the hare at position b. After one iteration the positions become a+1 and b+2 modulo λ. The difference increases by one modulo λ. Repeatedly adding one visits every residue class modulo λ, so one iteration eventually produces difference zero.

This proof matters because it identifies exactly which property makes the algorithm work: deterministic progress around one cycle and a relative speed difference coprime to the effective one-step gain.

5. Phase Two: Find the Cycle Entry

Detection tells us that a cycle exists, but the meeting point is not generally the entry. To find the entry, reset one pointer to the original start and leave the other at the meeting point. Then move both one step at a time. Their next meeting is the first cycle node.

The reason comes from the arithmetic of distances. At the first meeting, the hare has travelled twice as far as the tortoise. Their distance difference is therefore an integer number of whole cycle lengths. Rearranging that relation shows that the distance from the meeting point to the cycle entry, measured around the cycle, matches the tail length μ modulo λ. Advancing both one step preserves equality of remaining distance to the entry.

6. Find the Cycle Length λ

Once any pointer is known to be inside the cycle, hold one pointer fixed and move another until it returns to the same state, counting steps. That count is λ. Alternatively, Brent’s method discovers λ naturally during its first phase.

After λ is known, another common method for finding μ is to place two pointers at the start, advance one by λ steps, then move both one step at a time until they meet. The leading pointer remains exactly one cycle length ahead once both are in the loop, so they coincide at the entry.

7. Floyd Is Not a General Graph Cycle Detector

This boundary is essential. Floyd’s method assumes that from each state the algorithm follows one deterministic successor. In a general directed graph, a vertex may have many outgoing edges and the question “does this graph contain a cycle?” requires different machinery such as depth-first search, strongly connected components or topological reasoning.

Floyd solves cycle finding along one iterated successor relation, not arbitrary graph exploration.

8. Brent’s Algorithm: Change the Comparison Schedule

Brent’s cycle-finding algorithm keeps one reference point fixed for a block while the other pointer advances. The block length doubles through powers of two. When the moving pointer matches the reference, a cycle has been detected and the cycle length can be recovered.

Why care? Floyd may evaluate the successor function several times per loop iteration because the hare advances twice. If evaluating f is expensive, reducing the number of function calls can matter more than keeping the pseudocode maximally familiar.

9. Compare Floyd and Brent by the Cost That Matters

Memory: both use O(1) extra state under the standard model.
Code familiarity: Floyd is usually easier for beginners to recall and trace.
Successor evaluations: Brent can require fewer evaluations in many settings.
Cycle length: Brent’s structure naturally tracks λ.
Engineering choice: depends on whether successor evaluation, state comparison, branch behaviour or simplicity dominates the workload.

10. Applications Beyond Linked Lists

Detecting repetition in deterministic state machines.
Studying pseudo-random generator state sequences.
Finding periodic behaviour in iterative functions over finite domains.
Supporting Pollard-rho-style number-theoretic methods, where cycle behaviour helps reveal repeated states modulo an unknown factor.
Detecting loops in arrays or implicit functional graphs where each index maps to one next index.

The application may change, but the core contract stays the same: repeatedly apply one successor function and determine the eventual periodic structure.

11. Correctness: Separate Three Claims

Detection: if a reachable cycle exists, phase one eventually produces a meeting.
Entry: the reset-and-walk phase meets at the first cycle state.
Length: one complete lap from a cycle state returns after exactly λ successor steps.

Students often blend these claims into one vague proof. Treating them separately makes both reasoning and debugging much easier.

12. Complexity With the Right Variables

Let μ be the tail length and λ the cycle length. Floyd reaches a meeting after O(μ+λ) successor steps and uses O(1) extra memory. Finding the entry and length remains linear in the same reachable-structure scale.

Do not say merely “O(n)” unless n has been defined. For an implicit function sequence, the useful quantities are often μ and λ rather than the size of a container.

13. A Research-Informed Way to Learn It

Cycle finding is ideal for predict–trace–explain work. Research-informed computing pedagogy supports code reading and tracing before asking novices to write a full implementation from memory.

Predict: mark where the tortoise and hare will be after three iterations.
Run: trace a six-node list with a three-node cycle.
Investigate: explain the relative-distance change modulo λ.
Modify: move the cycle entry and predict what changes.
Make: implement detection first, then entry finding, then λ.
Transfer: replace linked-list next with a mathematical successor function.
Compare: implement Brent and count successor evaluations.

14. Testing Strategy

Empty list or no initial state, according to the language contract.
Single node with no cycle.
Single node pointing to itself.
Two nodes with a two-cycle.
Long tail leading into a short cycle.
No tail: start is already inside the cycle.
Cycle length one after a long tail.
Implicit function with known μ and λ.
Cross-check Floyd and Brent against a visited-set implementation on random finite functional graphs.

15. Engineering Details Professionals Notice

State equality may be expensive even when pointer equality is cheap.
The successor function can have side effects; cycle algorithms assume repeated evaluation is semantically safe.
Concurrent mutation of a linked structure can invalidate the reasoning.
A destructive or non-deterministic successor breaks the functional-graph model.
In distributed systems, observing an apparent repeated state does not automatically prove the entire global system has entered a deterministic cycle.

Common Failure States

Moving the hare only one step and expecting a collision argument based on relative speed.
Returning the first phase meeting point as the cycle entry.
Dereferencing two steps ahead without checking termination in a linked list.
Applying Floyd to an arbitrary graph with branching edges.
Memorising μ and λ formulas without understanding the distances they represent.
Claiming O(1) space while storing a growing trace for debugging in the production implementation.
Ignoring the cost of successor evaluation when comparing Floyd and Brent.

Practice Ladder: Beginner to Professional

Beginner: trace tortoise and hare positions on a drawn loop.
Foundation: detect whether a linked list contains a cycle.
Intermediate: locate the cycle entry and measure λ.
Intermediate: prove phase-one meeting using modular distance.
Advanced: generalize from pointers to an implicit function sequence.
Advanced: implement Brent and compare function-evaluation counts.
Professional: choose visited-set, Floyd or Brent based on memory, successor cost, state-comparison cost and reproducibility requirements.

Learning Hall Boundary

This article owns cycle finding in functional graphs and iterated deterministic sequences. It connects to the existing eduKateSengkang articles on linked structures, graph algorithms, number-theoretic algorithms and randomized methods without replacing their broader jobs.

Authoritative Starting Points

NIST and standard algorithms texts describe cycle detection as an elementary functional-graph technique.
Richard P. Brent, An Improved Monte Carlo Factorization Algorithm, BIT Numerical Mathematics 20 (1980), introduced the cycle-finding strategy now commonly called Brent’s algorithm.
Raspberry Pi Foundation computing pedagogy for research-informed use of code reading, tracing and structured progression.

Professional rule: you understand cycle finding when you can model the process as a functional graph, prove why Floyd’s pointers meet, derive the cycle entry and length, and choose between remembered history, Floyd and Brent based on the actual cost model.