Floyd's Cycle Detection Visualizer

How it works

1. Put both pointers on the head: slow = fast = head.
2. Phase 1: while fast and fast.next are not NULL, move slow one node and fast two nodes.
3. If fast runs off the end, the list is NULL-terminated — there is no cycle.
4. If slow == fast (the same node, not just the same value), a cycle exists.
5. Phase 2: move slow back to the head and advance both pointers one node at a time; the node where they meet is the start of the cycle.

Why the hare always catches the tortoise

If there is no cycle, fast reaches the end first — after about n/2 steps — and the algorithm stops. If there is a cycle, both pointers eventually enter it and can never leave. From then on, look at the distance from slow forward to fast around the loop: every step fast gains one node, so the gap shrinks by exactly one. A gap that shrinks by one per step cannot jump over zero, so the pointers must land on the same node, and they do so within one lap — before slow has gone once around the cycle. That bound is what makes phase 1 O(n).

Why phase 2 finds the start of the cycle

Let μ be the number of steps from the head to the first node of the cycle, λ the cycle's length, and suppose the pointers meet k steps past the cycle's start. At the meeting, slow has walked μ + k nodes and fast twice as many, 2(μ + k). The extra distance fast covered is a whole number of laps: 2(μ + k) − (μ + k) = μ + k = m·λ for some whole number m.

Rearranged, μ = m·λ − k. So a pointer standing at the meeting point that walks μ more steps has travelled k + μ = m·λ from the start of the cycle — whole laps — and lands exactly on the cycle's start. A second pointer walking μ steps from the head lands there too. Neither knows μ, and neither needs to: move both one step at a time and the first node they share is the answer.

Worked example

This page opens with 12 → 7 → 33 → 5 → 21 → 48 and the last node pointing back at index 2 (value 33), so μ = 2 and the cycle 33 → 5 → 21 → 48 has length λ = 4.

• Phase 1, step 1: slow = 7, fast = 33.
• Step 2: slow = 33, fast = 21.
• Step 3: slow = 5, fast = 33 (21 → 48 → back to 33).
• Step 4: slow = 21, fast = 21 — they meet, so there is a cycle. The meeting point is k = 2 steps past 33, and μ + k = 4 = 1·λ, as the proof predicts.
• Phase 2: slow restarts at 12 while fast stays on 21. After one step slow = 7 and fast = 48; after two, both are on 33.

They meet on 33 after μ = 2 steps: the cycle starts at index 2, and walking once around from 33 back to 33 gives its length, 4. Press play to watch both phases; the demo removes the extra link again when it finishes.

Cycle length and removing the cycle

Once you have a meeting point inside the loop, two more facts are cheap to get:

• Cycle length λ: keep one pointer fixed and walk the other until it comes back — λ steps.
• Remove the cycle: after phase 2 gives the start node, walk around the loop to the node whose next is the start and set that next to NULL. The list is an ordinary NULL-terminated list again.

Both add only O(λ) work and still use O(1) memory.

Alternatives: a hash set or Brent's algorithm

The obvious approach is to remember every node you visit in a hash set and stop when you see one twice. It is just as fast — O(n) — and finds the start of the cycle immediately, but it needs O(n) extra memory. Floyd's algorithm trades that memory for a second pass.

Brent's algorithm refines the idea: it moves one pointer and periodically teleports the other to it at power-of-two intervals, still with O(1) memory and usually fewer steps. Both algorithms work on any sequence produced by repeatedly applying a function, x → f(x), which is why the same idea appears in Pollard's rho factoring, in the analysis of pseudo-random number generators, and in the interview problem "find the duplicate number" (LeetCode 287), where array values act as next pointers.

Common mistakes

• Double-stepping without a NULL check. Reading fast.next.next when fast.next is NULL crashes on an even-length list; test fast and fast.next before every double step.
• Comparing values instead of nodes. Two different nodes may hold the same number; compare identity (is in Python, pointer equality in C).
• Starting the pointers on different nodes, for example fast = head.next. Detection still works, but the phase-2 arithmetic no longer lines up and the reported start node is wrong.
• Forgetting the empty list, or a one-node list without a self-loop.

Time and space complexity

Floyd's Cycle Detection in Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # next node


class LinkedList:
    def __init__(self):
        self.head = None  # first node

    def detect_cycle(self):
        slow = fast = self.head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        if fast is None or fast.next is None:
            return None  # they never met: no cycle
        slow = self.head
        while slow is not fast:  # 1 step each
            slow = slow.next
            fast = fast.next
        return slow  # cycle start

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.
• Reverse a Linked List — Step by StepReverse a linked list in place with three pointers. Watch every arrow flip step by step and compare iterative vs recursive code — O(n) time, O(1) space.
• Circular Linked List VisualizerCircular linked list visualizer: the last node points back to the head. See O(1) insert at both ends with a tail pointer, safe traversal and real-world uses.
• DFS Visualizer — Depth-First SearchDepth-first search explores a graph by going as deep as possible, then backtracking. See DFS step by step with discovery and finish times, back edges and code.