Every time I’ve had to figure out whether a linked list loops back on itself, or whether a sequence generated by repeatedly applying a function eventually falls into a repeating cycle, I’ve reached for Floyd’s Cycle Detection Algorithm. It’s often nicknamed the “tortoise and hare” algorithm because of how vividly it captures the idea of two pointers moving at different speeds. What I appreciate most about it is how little it asks for: no extra memory to store visited nodes, no hashing, just two pointers and a loop. That makes it a favorite in interviews and in real production code where memory matters.
History and Background
I attribute this algorithm to Robert W. Floyd, a computer scientist who made numerous fundamental contributions to the theory of programming languages and algorithms, including work that led to Hoare logic style reasoning. Floyd is widely credited with this technique around the 1960s, although the exact publication history is murky — it appears more as a piece of algorithmic folklore attributed to him than a single clean paper, and Donald Knuth documented it in “The Art of Computer Programming.” A related and more communication-efficient variant, Brent’s algorithm, was published later by Richard P. Brent in 1980 as an improvement, but Floyd’s version remains the one most people learn first because of its conceptual simplicity.
Problem Statement
I want to determine whether a sequence — most commonly represented as a linked list or as the iterates of a function f applied repeatedly starting from some value x0 — eventually enters a cycle, and if so, I often also want to know where the cycle begins and how long it is. The naive approach is to store every visited node or value in a hash set and check for repeats, which costs O(n) extra space. Floyd’s algorithm solves the same problem using only O(1) extra space, which matters enormously when I’m working with memory-constrained systems or extremely long sequences.
Core Concepts
- Sequence as a functional graph: I think of the list or iteration as a graph where each node has exactly one outgoing edge (
nextpointer, orf(x)). Such a graph either terminates, or eventually enters a cycle (it can never branch since each node has out-degree 1). - Tortoise: the slow pointer, which advances one step at a time.
- Hare: the fast pointer, which advances two steps at a time.
- Cycle: a sequence of nodes that repeats indefinitely once entered.
- Rho shape (ρ): the typical shape of such a sequence — a “tail” leading into a “loop” — which is literally why this family of problems is sometimes called “rho detection.”
- Mu (μ): the length of the tail before the cycle starts.
- Lambda (λ): the length of the cycle itself.
How It Works
I run this in two distinct phases:
- Phase 1 — Detect whether a cycle exists. I set both tortoise and hare at the start. I move the tortoise one step and the hare two steps on each iteration. If the hare ever reaches the end (a null pointer, in a linked list), there is no cycle. If the hare and tortoise ever point to the same node, a cycle exists.
- Phase 2 — Find the start of the cycle. Once a meeting point is found, I reset one pointer to the head/start and leave the other at the meeting point. I then advance both one step at a time; the node where they meet again is exactly the start of the cycle.
Optionally, a third phase can measure the cycle’s length by keeping one pointer fixed at the cycle start and moving another around the loop until it returns.
Working Principle
The mechanism relies on relative speed. Since the hare moves twice as fast as the tortoise, once both are inside the cycle, the hare gains one extra step on the tortoise every iteration. Because the cycle has finite length λ, the gap between them (measured going forward around the cycle) shrinks by one each step, so it must eventually hit exactly zero — meaning they meet. This is the same principle as two runners on a circular track: a faster runner will always eventually lap a slower one on a closed loop.
The reason the second phase correctly finds the cycle’s start point is more subtle and is proven using modular arithmetic on the tail length μ and cycle length λ, which I detail in the mathematical foundation below.
Mathematical Foundation
Let μ be the length of the tail before the cycle, and λ be the length of the cycle. When the tortoise has taken μ steps, it is exactly at the cycle’s start. The hare, moving twice as fast, has taken 2μ steps by then.
The meeting point in Phase 1 occurs after the tortoise has traveled some distance d where:
$$ d \equiv 2d \pmod{\lambda}, \quad d \geq \mu $$
which simplifies to:
$$ d \equiv 0 \pmod{\lambda} $$
So the meeting point is μ + k steps into the cycle for some non-negative integer k, and this position is congruent to 0 mod λ steps past the cycle start when measured from the tortoise’s total distance, meaning the meeting point is (λ - μ mod λ) steps into the cycle from the start.
For Phase 2, I use the identity that if I start a new pointer at the head (distance μ from the cycle start) and keep the meeting-point pointer where it is, both moving one step at a time, they will meet exactly at the cycle’s start after μ further steps — because:
$$ \mu + (\text{meeting offset}) \equiv \mu \pmod{\lambda} $$
holds precisely due to the congruence derived above. This is the elegant number-theoretic core that makes Phase 2 work.
Diagrams
flowchart TD
A[Start: tortoise = head, hare = head] --> B{hare and hare.next exist?}
B -- No --> C[No cycle]
B -- Yes --> D[tortoise = tortoise.next; hare = hare.next.next]
D --> E{tortoise == hare?}
E -- No --> B
E -- Yes --> F[Cycle detected]
F --> G[Reset pointer1 = head]
G --> H[pointer2 = meeting point]
H --> I{pointer1 == pointer2?}
I -- No --> J[pointer1++, pointer2++]
J --> I
I -- Yes --> K[This node is the cycle start]
Pseudocode
function hasCycle(head):
tortoise = head
hare = head
while hare != null and hare.next != null:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return findCycleStart(head, tortoise)
return null // no cycle
function findCycleStart(head, meetingPoint):
p1 = head
p2 = meetingPoint
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1 // start of the cycle
Step-by-Step Example
Consider a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (the 5 points back to 3, forming a cycle). Here μ = 2 (nodes 1, 2 are the tail) and λ = 3 (the cycle is 3, 4, 5).
Phase 1:
| Step | Tortoise | Hare |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 4 | 4 |
At step 3, tortoise and hare both land on node 4 — a meeting point confirms the cycle exists.
Phase 2:
I reset p1 to the head (1) and keep p2 at the meeting point (4).
| Step | p1 | p2 |
|---|---|---|
| 0 | 1 | 4 |
| 1 | 2 | 5 |
| 2 | 3 | 3 |
They meet at node 3, which is indeed the correct start of the cycle.
Time Complexity
- Best case:
O(1)if a very short cycle is found almost immediately (rare, and typically still bounded by list traversal). - Average case:
O(n), wherenis the total number of nodes visited before either detecting the cycle or reaching the end. - Worst case:
O(n)— the hare can never take more than roughlyμ + λsteps before either meeting the tortoise or exiting the structure, so the algorithm is strictly linear.
Space Complexity
This is the defining advantage of the algorithm: it uses only O(1) extra space, since it needs just two pointer variables regardless of how large the list or sequence is. This contrasts sharply with a hash-set-based cycle detection approach, which needs O(n) space to remember visited nodes.
Correctness Analysis
I prove correctness in two parts. First, I show that if a cycle exists, the hare and tortoise must eventually coincide: once both pointers are inside the cycle, their positions modulo λ converge because the hare’s relative speed advantage of one step per iteration guarantees the gap between them (mod λ) hits zero within at most λ iterations — this follows from the pigeonhole principle applied to a finite cyclic group. Second, the correctness of the cycle-start-finding phase follows directly from the modular arithmetic identity I derived earlier: distance from head to cycle start (μ) and distance from the meeting point back to the cycle start, when advanced simultaneously, land on the same node precisely because the meeting point is offset from the cycle start by a distance congruent to -μ mod λ.
Advantages
- Uses only constant extra memory, unlike hashing-based approaches.
- Simple two-pointer logic that is easy to implement correctly once understood.
- Naturally extends to also compute the exact cycle length and the tail length.
- Works on any “functional graph” structure, not just linked lists — including iterated function sequences used in cryptography (e.g., Pollard’s rho algorithm for factorization).
Disadvantages
- Requires two full traversals in the worst case (one to detect, one to locate the cycle start), which, while still
O(n), has more constant-factor overhead than a single-pass hash-set approach. - Slightly harder to reason about correctness at first glance compared to simply marking visited nodes.
- Doesn’t directly give the cycle length without a third pass (though this is a minor extension).
- Not naturally parallelizable, since each step strictly depends on the previous.
Applications
- Detecting loops in singly linked lists, which is a very common technical interview question.
- Cycle detection in iterative pseudo-random number generators, useful for identifying weak generators with short periods.
- Pollard’s rho algorithm for integer factorization, which reuses this exact two-pointer trick on a sequence generated by a polynomial function modulo
n. - Detecting infinite loops in state machines or game simulations where states form deterministic transitions.
- Memory leak or corrupted pointer detection in low-level systems programming.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
/* Detect whether a cycle exists; if so, return the meeting node, else NULL */
struct Node* detectCycleMeetingPoint(struct Node *head) {
struct Node *tortoise = head;
struct Node *hare = head;
while (hare != NULL && hare->next != NULL) {
tortoise = tortoise->next; /* one step */
hare = hare->next->next; /* two steps */
if (tortoise == hare) {
return tortoise; /* cycle confirmed */
}
}
return NULL; /* hare reached the end, so no cycle */
}
/* Given a meeting point inside the cycle, find the exact start node */
struct Node* findCycleStart(struct Node *head, struct Node *meetingPoint) {
struct Node *p1 = head;
struct Node *p2 = meetingPoint;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1; /* this is the start of the cycle */
}
struct Node* newNode(int data) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
int main() {
/* Build list 1 -> 2 -> 3 -> 4 -> 5 -> back to 3 */
struct Node *n1 = newNode(1);
struct Node *n2 = newNode(2);
struct Node *n3 = newNode(3);
struct Node *n4 = newNode(4);
struct Node *n5 = newNode(5);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n3; /* creates the cycle */
struct Node *meet = detectCycleMeetingPoint(n1);
if (meet != NULL) {
struct Node *start = findCycleStart(n1, meet);
printf("Cycle detected, starting at node with value: %d\n", start->data);
} else {
printf("No cycle detected.\n");
}
return 0;
}
Sample Input and Output
Input: Linked list 1 -> 2 -> 3 -> 4 -> 5, with node 5‘s next pointer set back to node 3.
Output:
Cycle detected, starting at node with value: 3
Optimization Techniques
- Brent’s algorithm: instead of moving both pointers every iteration, Brent’s variant grows the step size in powers of two, which in practice reduces the number of pointer comparisons and function evaluations, especially useful when each “step” (like evaluating
f(x)) is expensive. - Early exit tuning: in Phase 1, checking
hare == nullbefore dereferencinghare->nextavoids null pointer crashes on odd-length non-cyclic lists. - Combining detection and length calculation: I can compute cycle length in the same pass as detection by counting steps from the meeting point back to itself, avoiding a separate traversal.
- Iterative function application: when applying Floyd’s algorithm to functions rather than linked lists (e.g., in Pollard’s rho), caching
f(x)computations can save redundant work if function evaluation is costly.
Common Mistakes
- Forgetting to check
hare->next != NULLbefore advancinghareby two steps, which crashes on lists with even length and no cycle. - Assuming the meeting point found in Phase 1 is the cycle’s start — it is not, in general; Phase 2 is required.
- Mixing up which pointer to reset in Phase 2 (it should be the pointer that starts from the head, not the one at the meeting point).
- Applying this only to linked lists and not recognizing it generalizes to any deterministic, single-successor iteration (a common missed application in numeric algorithms).
Further Reading
- Knuth, D. E. “The Art of Computer Programming, Volume 2: Seminumerical Algorithms,” Section on cycle detection.
- Brent, R. P. “An improved Monte Carlo factorization algorithm,” BIT Numerical Mathematics, 1980: https://link.springer.com/article/10.1007/BF01933190
- GeeksforGeeks, “Floyd’s Cycle Finding Algorithm”: https://www.geeksforgeeks.org/dsa/floyds-cycle-finding-algorithm/
- Wikipedia, “Cycle detection”: https://en.wikipedia.org/wiki/Cycle_detection
