Floyd’s Cycle Detection Simplified

🧠 Ever wondered how to detect infinite loops in a linked list without extra memory?

Meet Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm — a brilliantly simple and efficient solution to a tricky problem.

🌀 What is Floyd’s Algorithm?

Floyd’s algorithm is a pointer-based technique for detecting cycles in a sequence, such as a linked list. It uses two pointers moving at different speeds. If there's a loop, the fast one eventually catches up with the slow one.

It was introduced by Robert W. Floyd in 1967 and is still taught today in algorithm and interview prep courses for its cleverness and efficiency.

🐢🐇 Tortoise and Hare Metaphor

Here's the core idea:

The tortoise moves one step at a time.
The hare moves two steps at a time.

If there's no cycle, the hare will hit the end. But if there's a loop, the hare will eventually meet the tortoise inside the cycle.

✅ When Should You Use It?

To detect cycles in singly linked lists
In state machines or function iterations
When you want O(1) space (no hash sets)
To find infinite loops in algorithms or generators

🧑‍💻 Code Example in C++

Node* tortoise = head;
Node* hare = head;

while (hare != nullptr && hare->next != nullptr) {
    tortoise = tortoise->next;
    hare = hare->next->next;

    if (tortoise == hare) {
        // Cycle detected
        break;
    }

    tortoise = head;
    while (tortoise != hare) {
        tortoise = tortoise->next;
        hare = hare->next;
    }
}

🧩 Real-World Uses

Detecting infinite loops in state machines.
Finding repeated values in pseudo-random number generators.
Linked list corruption detection in memory-managed languages.
Cycle detection in functional graphs, such as f(x) = next(x) iterations.

⚖️ Time and Space Complexity

Metric	Value
Time	O(n)
Space	O(1)

⚠️ Gotchas and Edge Cases

Always check hare != null and hare.next != null to avoid NullPointerException.
For finding the start of the loop, ensure the cycle was detected first.
Not ideal for graphs with multiple cycles and branches — better for single-path traversal like linked lists.

🧘 A Philosophical Thought

Floyd’s algorithm is a metaphor: life is full of loops, some hidden, some benign. Detecting them early — in code or in habit — can save us from going in circles.

🧩 TL;DR

Use Floyd’s algorithm to detect cycles with just two pointers.
It’s space-efficient and surprisingly powerful.
Great for linked lists, iterative functions, and cycle detection without extra memory.

💬 What’s Next?

Explore variations like:

Brent’s Algorithm (faster in some cases),
Cycle length detection,
Applications in graph theory and function iteration.

Floyd’s Cycle Detection Algorithm: The Tortoise, the Hare, and the Hidden Loop

Table of contents