Fast and Slow Pointer: Floyd's Cycle Detection Algorithm Explained

Scenario context

Move a slow pointer one step and a fast pointer two steps through a linked structure. If they ever meet, a cycle exists. Then reset one pointer to the head and advance both one step at a time — where they meet next is the cycle's start node. This single algorithm, invented by Robert Floyd in the 1960s, solves cycle detection, cycle start finding, linked list midpoint, and the Happy Number problem — all in O(n) time…

This walkthrough focuses on The Infinite Loop Problem: Detecting It Without Extra Memory.

Before making a design choice, clarify:

• Your production service is stuck.
• A background thread processes a linked list of tasks and never terminates.
• There's no log entry marking completion — it's just spinning.

Concepts in play: jvm-internals-and-garbage-collection, database-indexing, core-algorithm-patterns, graph-traversal-algorithms

Stage 1 — Visualizing Slow and Fast Pointers Converging in a Cycle

• Phase 1 detects the cycle; Phase 2 navigates both pointers to the exact start node using the F = kC − M invariant.
• Worked trace on 1 → 2 → 3 → 4 → 5 → 3 (cycle starts at node 3, index 2): Phase 2: pointer1 at node 1, pointer2 at node 4.
• Both advance: pointer1→2, pointer2→5.

flowchart TD
    A([Start: slow=head, fast=head]) --> B{fast != null AND fast.next != null}
    B -- No --> C([No cycle  list is acyclic])
    B -- Yes --> D[slow = slow.next fast = fast.next.next]
    D --> E{slow == fast?}
    E -- No --> B
    E -- Yes --> F([Cycle detected! Meeting point found])
    F --> G[Reset pointer1 = head pointer2 = meeting point]
    G --> H{pointer1 == pointer2?}
    H -- No --> I[pointer1 = pointer1.next pointer2 = pointer2.next]
    I --> H
    H -- Yes --> J([Cycle start node found])

Observable outcome: Both advance: pointer1→2, pointer2→5.

Stage 2 — Where Cycle Detection Shows Up in Real Systems

• Floyd's algorithm sounds academic, but it solves real engineering problems every day: Memory safety in embedded systems: Microcontrollers that traverse linked memory regions (free lists, task queues) use fast/slow point…
• A corrupted next pointer that forms a loop is detected in O(n) without any heap allocation — critical when heap is unavailable.
• Database cursor traversal: Some database engines internally represent result-set cursors as linked node chains.
• A corrupted cursor that loops back to an earlier record would spin indefinitely; the fast/slow check provides a cheap safety gate.

Observable outcome: A corrupted cursor that loops back to an earlier record would spin indefinitely; the fast/slow check provides a cheap safety gate.

Stage 3 — When the Speed Differential Approach Breaks Down

• Single-element cycles: If a node points to itself ( node.next == node ), slow and fast both jump to it on the first step.
• Detection still works, but Phase 2 boundary conditions need a null check before dereferencing pointer.next .
• Doubly linked lists: The fast.next.next step assumes a singly linked structure.
• In a doubly linked list with backward pointers, you'd need to be explicit about always following next (not prev ).

Observable outcome: In a doubly linked list with backward pointers, you'd need to be explicit about always following next (not prev ).

Stage 4 — Deciding Between Fast/Slow and Hash-Set Cycle Detection

• The one hard rule: fast/slow pointers require a deterministic single next function .
• Any structure where each node has exactly one successor and the successor relationship is stable is a valid candidate.

Observable outcome: Any structure where each node has exactly one successor and the successor relationship is stable is a valid candidate.

Stage 5 — How Java's Concurrent Utilities Use Cycle-Awareness

• Java's java.util.concurrent package deals with cycles in a different but related way.
• ForkJoinPool 's work-stealing deques and the LinkedBlockingDeque both perform internal consistency checks during debug builds to ensure that internal node chains don't form cycles — a condition that would cause the pool…
• The ReentrantLock implementation in java.util.concurrent.locks maintains a CLH (Craig, Landin, and Hagersten) queue of waiting threads as a linked chain of node objects.
• If a bug causes a node to point back to an earlier node in the queue, the lock's acquire() loop would never terminate — exactly the cycle problem Floyd's algorithm detects.

// Simplified version of how you might detect a cycle in a dependency graph
// using the fast/slow idea adapted for a Map-based "next" relationship
public boolean hasCycleInDependencies(String start, Map<String, String> dependsOn) {
    String slow = start;
    String fast = dependsOn.get(start);

    while (fast != null && dependsOn.get(fast) != null) {
        slow = dependsOn.get(slow);
        fast = dependsOn.get(dependsOn.get(fast));
        if (slow.equals(fast)) return true;
    }
    return false;
}

Observable outcome: If a bug causes a node to point back to an earlier node in the queue, the lock's acquire() loop would never terminate — exactly the cycle problem Floyd's algorithm detects.

End-to-end outcome

After working through the stages, you should be able to explain:

• Always check fast != null && fast.next != null .
• Checking only fast != null will crash on even-length lists when fast.next.next dereferences a null next .
• • Two-phase structure: Phase 1 detects the cycle (O(n)).
• Phase 2 finds the cycle start using the F = kC - M invariant (O(n)).

Alternatives considered

The source focuses on one primary design. A second architecture is not compared, so no alternative is invented here.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.