Floyd's Cycle-Finding Algorithm¶

A constant-extra-space method that advances two references at one and two steps along the same successor chain to detect a reachable cycle.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13234
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Algorithms, Data Structures → Computer Science & Software Engineering
Aliases: Tortoise and Hare Algorithm, Floyd's Tortoise and Hare

Core Idea¶

Floyd's cycle-finding algorithm, or the tortoise-and-hare method, asks whether repeatedly taking one successor from a specified start eventually revisits a state. It holds two references into that same sequence. The tortoise advances one successor step per round; the hare advances two. Their shared starting position is ignored. If they later point to the same state, the reachable sequence contains a cycle. If the successor can be absent, as at the end of an ordinary singly linked list, the hare's arrival at that end instead shows that no loop is reachable from the start.^[1]^[2]

For a total function on a finite state set, a revisit is guaranteed: there are only finitely many values, and every state has a next value. The orbit has a nonrepeating prefix of length $\mu$ followed by a repeating cycle of length $\lambda$. The first tortoise-hare meeting establishes that the orbit cycles, but the meeting state need not be the first cycle state. A second phase resets one reference to the start and advances both singly to find the entry; another walk around the loop counts its length when needed. John Burkardt's original cycle-finding software describes $\mu$ and $\lambda$ as separate outputs, and Cornell's linked-list exercise distinguishes first detection from the second intersection at entry.^[3]^[1]

This is one named method, not the whole subject of cycle detection. Brent's method uses a different comparison schedule, and a graph-search routine looking for any cycle among many outgoing edges solves a wider question. The historical attribution is also qualified: an original formalization calls the tortoise-and-hare algorithm ascribed to Floyd by Knuth; that wording does not establish that Floyd published this specific procedure.^[2]

Structural Signature¶

Sig role-phrases: chosen start → unique deterministic successor orbit → slow one-step reference and fast two-step reference → post-start equality or terminal test → optional entry/period passes → successor-work versus storage accounting.

Chosen start and unique successor. From the start, the method follows one specified next operation, producing one sequence. An arbitrary branching graph does not supply that sequence until a path-selection rule is added. The method only answers the question about the selected orbit.^[3]
Two moving references. The tortoise and hare hold current positions without retaining every previously seen state. They may be node addresses in a linked list or values in a finite mathematical iteration; equality must mean equality of the relevant state, not merely equality of displayed data in different nodes.^[1]^[4]
Unequal advancement. Advancing by one and two successor operations changes the references' relative positions by one place per round once both are on a cycle. If both moved equally from the same start, a later meeting would be uninformative.^[1]
A post-start decision. A later equality is a cycle witness. A partial successor chain must check for its terminal value before trying to advance beyond it. Equality of the two references before any motion is only their initialization, not evidence of a cycle.^[1]
Optional location and length. The collision need not equal the cycle entry. Resetting one reference to the start and moving both singly obtains the entry; a subsequent circuit can count the period. A caller wanting only a Boolean answer can stop at collision or termination.^[1]^[3]
Resource model. With constant-cost successor and equality operations, the detection and optional passes take $O(\mu+\lambda)$ successor rounds and a constant number of extra references. This counts auxiliary storage, not the memory needed to hold the underlying list or compute an expensive successor.^[1]^[4]

What It Is Not¶

It is not every kind of cycle detection. A depth-first search can inspect a branching directed graph for cycles outside any one deterministic successor path. Floyd's method can miss such a cycle because it has never followed that branch; its promise is only about the orbit it actually traverses. Nor is it the static cycle itself, which can exist independently of any procedure used to discover it.

It is not Brent's algorithm. The original formalization treats the Brent version separately; Burkardt maintains separate Floyd and Brent cycle-finding software. Both can use little auxiliary storage, but the two-speed comparison schedule is what identifies this entry.^[2]^[3]

It is not proof that every linked list loops. A finite total successor map must repeat, whereas a usual list may have a terminal null reference. The tortoise-and-hare test must include that case; the result then is no reachable loop, not an algorithm failure.^[3]^[1]

It is not a constant-time algorithm. Constant auxiliary space trades away the stored history of visited states; slow and fast traversal still perform successor evaluations, and locating the entry or period adds work. Any statement about time must say which operations are counted.^[4]^[1]

Scope of Application¶

The method applies when the question concerns the future of one deterministic chain from one start, and one can repeatedly obtain and compare successor states. A singly linked list is the data-structure case: each node has at most one next node, and the fast reference can encounter null. A finite computational iteration is the mathematical case: a state-transition function always supplies another state, so the question is where repetition begins and how long it lasts.^[1]^[3]

MIT's original mathematical lecture uses two-speed advancement during an iterated computation to avoid keeping a full collision-history table, explicitly contrasting a stored-state version with constant storage. That example shows transfer beyond linked-list addresses, but its number-theoretic objective and cost bounds belong to that particular computation; they are not part of Floyd's algorithm's definition.^[4]

Clarity¶

Ask three separate questions: Does the chosen orbit cycle? Where does it first enter a cycle? How long is the cycle? A first fast-slow equality answers the first, not necessarily the next two. Cornell's exercise explicitly makes the second intersection, after resetting a reference, a separate property. Burkardt's mathematical implementation names the entry distance $\mu$ and cycle length $\lambda$ as distinct quantities.^[1]^[3]

State whether the successor is total. In a total finite map, a cycle is inevitable and the method locates information about it. In a partially defined chain, the method also distinguishes loop from termination. This small modeling distinction prevents the common false assertion that the presence of finitely many list nodes alone guarantees a loop.

Manages Complexity¶

The method compresses the question of repeated states from “keep every visited position and check whether the next is old” to “keep two positions and make their relative displacement change.” On a cycle of length $\lambda$, the hare gains one cycle position on the tortoise each round; they eventually coincide. Before the cycle, the method does not need a history table to preserve evidence of past positions. This is the complexity it manages: storage of history, not the cost of generating successors.^[1]^[4]

The compression has a price. The hare may evaluate the successor twice per round, and a caller requiring entry and length makes further passes. If a successor is expensive, a visited-state table or another cycle-finding schedule may be preferable. The method therefore separates space economy from total work rather than declaring either approach uniformly best.

Abstract Reasoning¶

Model the reachable states as $x_0,x_1,x_2,\ldots$ with $x_{i+1}=f(x_i)$ while a successor exists. If this is a total function over a finite set, pigeonhole reasoning gives a first repeat. The repeated tail forms a cycle because applying the same deterministic $f$ to equal states produces equal subsequent states. Let $\mu$ be the number of steps before the cycle and $\lambda$ its period.^[3]

Once both references are on that cycle, their relative offset grows by one modulo $\lambda$ each round, so within a circuit it becomes zero. This explains detection without storing the entire past. At a meeting reached after $t$ slow steps, the hare has advanced $2t$, so the distance $t$ between their traversed positions is a multiple of $\lambda$. Resetting one reference to $x_0$ and moving both one step at a time then makes them agree at the entry after $\mu$ further steps. The argument assumes a deterministic successor and state equality; it does not transfer unchanged to a stochastic path that can branch on repeated visits.^[1]

For a partial chain, short-circuit the fast advancement when its next node does not exist. If it ends, the reachable chain is acyclic. This is a different stopping proof from eventual meeting on a finite total orbit, but the two outcomes are produced by one guarded two-reference procedure.^[1]

Knowledge Transfer¶

The same role map moves from memory pointers to abstract state values. In a list, “successor” is a node's next field and “equality” should compare node identity. In a finite iterated function, “successor” is one function evaluation and “equality” compares states under the model's correct equivalence relation. MIT's iterated mathematical computation uses the latter form, while Cornell's list exercise uses the former.^[4]^[1]

The transferable part is the schedule and collision argument, not each setting's application goal. A list programmer may only want to know whether a malformed chain loops; a mathematical computation may need an entry index or period. A graph with several outgoing edges lacks the unique-next role, and an algorithm that searches all branches needs a different coverage argument.

Examples¶

Singly linked list with a back-link¶

Consider node references $A\to B\to C\to D\to B$. Starting both references at $A$, compare them only after advancement. The slow reference visits $B,C,D$ while the fast reference visits $C,B,D$; their first later meeting is at $D$, not at the entry $B$. Resetting one to $A$ and moving both one step gives $B$; walking $B\to C\to D\to B$ counts a three-node cycle. If $D$ instead points to null, the guarded fast path terminates and reports no reachable loop. This is a constructed illustration of Cornell's linked-list method, not a quoted source example.^[1]

Mapped back: start $A$ → unique next-pointer chain → two node references → one/two next steps → later collision at $D$ or null at the end → optional entry $B$ and length three → constant extra references.

Finite-state computational iteration¶

Let a deterministic finite map satisfy $0\mapsto1\mapsto2\mapsto3\mapsto4\mapsto2$ from start $0$; an unused state \$5$ maps to itself. The selected orbit has a two-step tail and a three-state cycle, so $\mu=2$ and $\lambda=3$. The two references hold state values, not list addresses. They meet after advancement; the optional reset-and-walk phase locates state $2$. The unused fixed point at \$5$ illustrates that this method says nothing about a different orbit it never visits. The numerical map is constructed here solely to show the roles; Burkardt supplies the finite-iteration, $\mu$, $\lambda$ model, and MIT supplies a distinct mathematical-computation use.^[3]^[4]

Mapped back: start state $0$ → deterministic map → two stored state values → one/two function evaluations → post-start equality → entry $2$ and period three → constant auxiliary state storage.

Near miss: a branching graph¶

Suppose a graph vertex has a branch toward a three-vertex directed cycle and another branch toward a terminal vertex. Choosing only the terminal successor creates one acyclic walk; its lack of a meeting cannot certify the whole graph is acyclic. The unique-successor representation of the whole search problem is missing.

Structural Tensions¶

Storage economy vs. successor work. The two references avoid a visited-state table, but the hare advances twice and location/period recovery requires extra traversals. A smaller memory footprint is not necessarily a faster computation. Diagnostic: How costly is one successor evaluation relative to storing and checking a visited state, and does the caller need existence alone or entry and period too?^[4]^[1]
One-orbit certainty vs. graph-wide coverage. The algorithm is decisive for the chosen unique-successor chain, yet it cannot infer that a branching graph has no cycles elsewhere. Expanding coverage changes the problem and the needed search method. Diagnostic: Is every relevant state reached by repeated application of one specified successor from the given start, or are there other branches and components?

Structural–Framed Character¶

Carrier test: there is a computable successor chain from a chosen start. Transformation test: two references advance one and two steps per round without a visited-state table. Invariant test: equality after initialization is excluded, and once both are on a cycle their relative offset changes by one modulo its period. Failure test: a null fast path or an unrepresented graph branch invalidates a claimed positive/whole-graph conclusion. Transfer test: the schedule applies both to linked-node addresses and to values of a finite iterated function.^[1]^[3]

Its character: structurally crisp but domain-framed as a computational method. On the five Structural–Framed criteria: vocabulary travels only where successor, state equality and stored references make sense; evaluative weight is conditional on the time-space trade; institutional origin is mathematical/computer-science algorithm design, not a social rule; human-practice bound is modest because a designer selects the representation and outputs; and import versus recognize favors direct recognition across computational substrates but only analogy beyond successor-based computation. The named method remains domain-specific, not a Prime.

Structural Core vs. Domain Accent¶

The core is a deterministic unique-successor orbit plus two unequal-rate references and a properly timed equality/termination test. A list's node addresses and null marker are one accent; a number-theoretic or finite-state computation's evaluated state values are another. The optional entry and period calculations extend the core without changing the two-speed detection identity.

The distinction matters because “cycle detection” also names broader tasks with different inputs and guarantees. A DFS back-edge test searches a graph's branching edges; Brent's algorithm uses a different cycle-finding schedule. Calling either one “Floyd's method” loses the specific operational structure.^[2]^[3]

This entry is a kind of Algorithm.

The broader abstraction is Algorithm: Floyd's method has specified inputs, effective successor/equality steps, a stopping report, and a resource profile. It narrows the general procedure to a particular two-reference schedule on one orbit. Prime:cycle is the object that may be detected, but not a strict parent of the method because the method also has a meaningful negative result on a null-terminated list. Prime:iteration describes the repeated successor process but does not identify this particular detector. The live Search Algorithm entry requires state-space frontier exploration and a goal-test strategy, neither of which is necessary here; it is a neighbor, not a forced parent.

Relationships to Other Abstractions¶

Current abstraction Floyd's Cycle-Finding Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Floyd's Cycle-Finding Algorithm is a kind of Algorithm Prime

Floyd's two-speed successor procedure is a specific algorithm for deciding whether one reachable orbit repeats.

Hierarchy paths (2) — routes to 2 parentless roots

Floyd's Cycle-Finding Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Floyd's Cycle-Finding Algorithm sits in a sparse region of the domain-specific corpus (62^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Distributed Systems Theorems & Fallacies (19 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

General cycle detection: the umbrella problem, including graph-search and other sequence methods.
Brent's cycle-finding method: another constant-storage method with a different comparison schedule.^[2]^[3]
Floyd–Warshall algorithm: an unrelated all-pairs shortest-path procedure despite the shared name Floyd.
A periodic sequence itself: a mathematical object; Floyd's method is one way to discover its reachable repetition.
Two pointers moving through any list: the one/two advancement, post-start comparison and termination guard are the diagnostic commitments.

References¶

[1] Cornell CS 2110, “Linked Data,” lecture 13, original course material, exercise 13.11 parts (a)–(e), on tortoise-and-hare linked-list detection, terminal behavior and the second intersection. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r

[2] Peter Gammie, “The Tortoise and Hare Algorithm”, Archive of Formal Proofs (2015), original abstract and formalization session headings; states the algorithm is ascribed to Floyd by Knuth and distinguishes Brent's improved version. registry ↩a ↩b ↩c ↩d ↩e

[3] John Burkardt, “CYCLE_FLOYD — Cycle Detection by Floyd's Method”, original author-maintained software description, opening discussion of finite iteration, $\mu$ and $\lambda$, with separate CYCLE_BRENT link. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l

[4] MIT Mathematics 18.783, Lecture 9 slides, original course PDF, pp. 13–14, on two-speed cycle detection in iterated mathematical computation and constant auxiliary storage. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h