Cycle Detection: Complete Guide with Floyd's Algorithm

Cycle detection tells you whether a path loops back on itself. In a linked list, that means a corrupted pointer that never reaches null. In a dependency graph, it means a circular prerequisite that makes a build or course schedule impossible. Every working developer runs into infinite loops and circular references. Knowing how to find the cycle fast is the difference between a five-minute debug session and an hour of head-scratching.

Definition: cycle detection is a family of algorithms that determine whether a data structure (linked list, directed graph, undirected graph, or state machine) contains a path that eventually revisits a node or state you have already visited.

Real-World Analogy

Picture two runners on a track. If the track is a straight line, the faster runner reaches the finish first and the slower runner finishes after. They never cross paths again after the start. If the track is a loop, the faster runner will eventually lap the slower one from behind, because there is no finish line to exit through.

That is exactly how Floyd’s tortoise and hare algorithm works. Two pointers move through the data at different speeds. One moves one step per iteration, the other moves two steps. If they land on the same node, a cycle exists. If the fast pointer ever reaches a dead end (null), the structure is cycle-free.

Visual Explanation

Here is how the two pointers probe a linked list for a cycle.

    graph TD
    I["Initialize slow = head, fast = head"] --> C{"fast != null && fast.next != null?"}
    C -->|Yes| M["slow = slow.next<br/>fast = fast.next.next"]
    M --> D{"slow == fast?"}
    D -->|Yes| E["Cycle detected"]
    D -->|No| C
    C -->|No| F["No cycle (fast reached end)"]
  

The key insight is that in a cycle, the fast pointer gains on the slow pointer by exactly one node per iteration. The gap shrinks until they meet, no matter how long the non-cyclic tail is before the loop starts.

For graph cycle detection, the approach changes. Instead of two pointers, we track node states during a depth-first search.

    stateDiagram-v2
    direction LR
    [*] --> Unvisited
    Unvisited --> Visiting: Start DFS on node
    Visiting --> Visited: All neighbors processed
    Visiting --> Visiting: Back edge to Visiting node = cycle
    Visited --> [*]
  

A back edge to a node that is currently being visited (in the recursion stack) means a cycle exists in a directed graph. For undirected graphs, a back edge to any previously visited node that is not the direct parent also signals a cycle.

When to Use This Pattern

Reach for cycle detection when the problem has one of these characteristics.

• A linked list is involved and the problem asks whether it terminates or has a loop. Floyd’s algorithm handles this in
  O(1)
  space.
• The problem models a dependency graph (courses, build steps, task scheduling) and you need to verify it is a DAG. DFS state tracking or Kahn’s algorithm will detect any cycles.
• An undirected graph must be checked to see if it forms a valid tree. A tree has exactly n-1 edges and no cycles. Union-Find detects cycles in undirected graphs efficiently.
• You need to find a repeated number in an array where values range from 1 to n. The “find the duplicate number” problem is secretly a linked list cycle in disguise, and Floyd’s algorithm applies directly.
• The input involves a state machine or iterative function that might loop forever. Any structure where the same state can repeat signals a cycle detection approach.

Complexity Analysis

The cost of cycle detection depends on whether you are working with a linked list or a graph.

The time is linear in the size of the structure for all three methods. Each node and edge is visited at most once. Floyd’s stands apart on space because it uses only two pointer variables regardless of input size. Graph methods need at least a visited flag per node, and directed graph detection also needs a per-node recursion-stack marker.

Common Mistakes

Using Floyd’s on a singly linked node that is not a proper ListNode. Floyd’s assumes each node has a next pointer. If you try to use it on an array or a custom structure where nodes are not explicitly linked, the pointer movement does not make sense. Check that the data structure actually has a next-like reference before writing the while loop.

Forgetting that Floyd’s detects cycles but does not always find the start by itself. Phase 1 of Floyd’s finds whether a cycle exists. Phase 2 (resetting one pointer to head and moving both one step at a time) finds where the cycle begins. Many candidates stop after phase 1 when the problem asks for the cycle entry node, which costs them the solution to Linked List Cycle II.

Confusing visiting state with visited state in directed graph DFS. A back edge to a node that is fully processed (visited state) is fine; it is just a cross edge or forward edge. Only a back edge to a node that is still in the recursion stack (visiting state) signals a cycle. Using a single boolean visited array for a directed graph will produce false positives.

Not handling the modulo in Array-to-Linked-List mapping. When using Floyd’s on an array-based problem like Find the Duplicate Number, the value at each index tells you the next index to visit. Failing to map this correctly or running the fast pointer twice as fast through this index arithmetic leads to index-out-of-bounds or infinite loops.

Related Patterns

• Two Pointers . Floyd’s algorithm is a specific case of the two-pointer technique where the pointers move at different speeds. The general two-pointer pattern covers opposite-end and same-direction pointer setups for sorted arrays and sliding windows.
• Graph Traversal . DFS and BFS are the foundation for graph cycle detection. The graph traversal page covers adjacency lists, visited tracking, and the traversal mechanics that cycle detection builds on.
• Union Find . For undirected graph cycle detection, Union-Find is often simpler than DFS. The Union-Find page covers the disjoint-set data structure and its application to connectivity and cycle detection.

Next Steps

Now that you understand the theory, the code templates give you memorizable implementations of Floyd’s algorithm, DFS cycle detection, and Union-Find in 6 languages. Then work through the practice problems to apply the pattern to real interview questions.