Offensive Security Researcher & Quantum Cryptography Analyst

Floyd Cycle Detection Algorithm: Working, Explanation, and Linked List Cycles

Abdul Wahab Junaid
floyd cycle detection algorithm and working of this algorithm

floyd cycle detection algorithm and working of this algorithm

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

How It Works

I run this in two distinct phases:

  1. 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.
  2. 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:

StepTortoiseHare
011
123
235
344

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).

Stepp1p2
014
125
233

They meet at node 3, which is indeed the correct start of the cycle.

Time Complexity

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version