Floyd's Cycle Detection Algorithm: Two Pointers, One Rule

You have a linked list. Someone asks: does it loop? The obvious answer is a hash set. Visit every node, record each address, panic when you see one you've already seen. That works. It's O(n) time and O(n) space.

Now imagine your interviewer smiles and says: "Can you do it in O(1) space?" That smile means you're about to discover Floyd's cycle detection algorithm, whether you want to or not.

Floyd's Tortoise and Hare algorithm detects a cycle in a linked list using just two pointers, in O(n) time and O(1) space. No extra memory. No hash set. Two runners, one rule: the fast one moves twice as fast, and if there's a cycle, they will always meet.

This is Part 1: detecting the cycle and understanding why the proof works. Part 2 covers finding exactly where the cycle starts.

A meme showing: "learning dynamic programming / look up tutorial / so we use hash set" with a confused cat

Every algorithm tutorial, eventually. This one won't.

The Algorithm in 30 Seconds

Start both pointers at the head. Advance slow by one node per step. Advance fast by two nodes per step. If fast or fast.next reaches null, there's no cycle. If slow == fast at any point, there's a cycle.

That's it. The hard part is believing the guarantee.

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Go ahead and run this on a list with a cycle. They will meet. Now the interesting question: why are you so sure?

How Floyd's Cycle Detection Works

The Setup

Linked list nodes live at arbitrary memory addresses. There's no index. The only way to traverse is to follow next pointers. A "cycle" means some node's next pointer points back to a node you've already visited. The list no longer terminates.

Linked list with a cycle: nodes A and B form the tail, then C, D, E loop back to C

A→B form the tail (length 2). C→D→E→C is the cycle (length 3). E.next points back to C, so traversal never ends.

Two Phases

Phase 1 (this article): detect that a cycle exists. The two pointers meet somewhere inside the cycle.

Phase 2: find exactly which node is the cycle's entry point. That's a separate move, covered in Part 2.

The Relative Speed Frame

This is the key mental model. Think of both pointers as runners on a circular track, and consider fast's position relative to slow.

Eventually slow reaches the cycle entry. Fast is already somewhere inside by then: it moves at double speed, so it entered the cycle first. The cycle is now a closed loop of length L.

Three frames showing slow (blue) and fast (orange) on a circular track: gap=3 at step 0, gap=2 at step 1, gap=1 at step 2

Each step, slow moves one node, fast moves two. The gap shrinks by exactly one per step. A finite gap must eventually hit zero.

Fast is somewhere ahead of slow on this circular track. Call the gap g (the number of nodes between slow and fast, going forward along the cycle). Every step:

Slow moves 1 position forward.
Fast moves 2 positions forward.
The gap closes by 1.

That's it. The gap decreases by exactly 1 each step. Since the cycle is finite, the gap must eventually reach 0. When g = 0, they're at the same node.

The Proof They Must Meet

Intuitive: The Closing Gap

When slow enters the cycle, fast is g steps ahead (where 0 <= g < L). Each step, g decreases by 1. Since g is a non-negative integer that keeps shrinking, it hits 0 in at most L steps. Done.

One thing to check: can the gap underflow? Could it go from 1 to... something weird? No. The gap is taken mod L (it's a circular track). Going from gap = 1 to gap = 0 just means they've landed on the same node. There's no "skipping past" each other, because each step the gap changes by exactly 1.

Arithmetic: The Formal Version

Proof diagram: tail of length a, cycle entry E, meeting point M with offset b from entry, cycle length L

Label variables:

a = distance from head to cycle entry (tail length)
L = cycle length
b = distance from cycle entry to the meeting point (within the cycle)

When the pointers meet inside the cycle:

Slow has traveled: a + b
Fast has traveled: a + b + n*L for some integer n ≥ 1 (fast looped around n more times)

Since fast travels twice as far as slow at every step:

2(a + b) = a + b + n*L
a + b = n*L

So a + b is a perfect multiple of the cycle length. This identity is also the key to Phase 2 (finding the cycle start), but for now the important takeaway is: for any cycle length L, there exists a step count where the equation holds. The meeting is guaranteed.

Why 2x Speed?

Any integer speed ratio greater than 1 works for detection. With fast at 3x, the relative gain per step is 2, and you'd still close the gap eventually. The 2x ratio is conventional because:

It's the smallest, so fast advances as slowly as possible (fewest "wasted" steps past the meeting point)
The Phase 2 math for finding the cycle start is cleanest at 2x
Less computation per step

Core Operations

Operation	Time Complexity	Space Complexity	Notes
Detect cycle	O(n)	O(1)	Phase 1
Detect cycle (hash set)	O(n)	O(n)	Comparison baseline
Find cycle start	O(n)	O(1)	Phase 2, Part 2
Find cycle length	O(n)	O(1)	Walk cycle after meeting
Find middle of list	O(n)	O(1)	Variant, no cycle needed

Why O(n) Time Holds

The total step count has two parts.

Tail traversal: Slow takes a steps to reach the cycle entry. Fast entered the cycle earlier (it moves twice as fast) and is already circling by the time slow arrives. The tail phase is a steps.

Cycle convergence: Once slow enters the cycle, the gap is at most L - 1. It closes at 1 step per iteration. So at most L more steps to meet.

Total: a + L ≤ n + n = O(n). Linear, always.

Why O(1) Space

Two pointer variables. That's it. No visited set, no recursion stack, no auxiliary array. The space usage is constant regardless of list size.

One Structure, Every Language

The core operation shown in each implementation: detect a cycle in a singly linked list. Each builds its own node type since LeetCode's ListNode varies by environment.

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class ListNode:
    val: int
    next: Optional[ListNode] = None

def has_cycle(head: Optional[ListNode]) -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Note is instead of == here. We're comparing object identity (same node in memory), not equality of values. Two nodes can hold the same value but be different nodes. Use is.

What Problems It Solves

The fast/slow pointer technique applies to any problem that can be modeled as "does following a sequence of steps from some starting state eventually revisit a state?"

Explicit cycle detection in linked lists. The canonical use case. Any time you need to determine if following next pointers would loop forever.

Implicit cycle detection in functional sequences. The sequence doesn't have to be a linked list. If you have a function f(x) and you generate x, f(x), f(f(x)), ..., Floyd's algorithm can detect whether this sequence eventually repeats. This is how it applies to the Happy Number problem (LeetCode 202).

Finding the middle of a linked list. When fast reaches the end, slow is at the middle. No cycle needed. Single-pass, O(1) space.

Detecting palindromes in linked lists. Find the middle (using fast/slow), reverse the second half, compare. O(n) time, O(1) space.

Finding duplicate numbers. LeetCode 287. An array where values are in range [1, n] can be interpreted as a functional graph: index i points to nums[i]. A duplicate creates a cycle. Floyd finds it.

Recognizing the Pattern

Ask these questions when you see a linked list or a sequence problem:

Do I need to detect if traversal loops?
Do I need the midpoint of a list?
Does the problem say "O(1) space" or "without modifying the list"?
Can I express this problem as "follow function f repeatedly starting from x"?

If yes to any of those, reach for fast/slow pointers.

Worked Example 1: Linked List Cycle (LeetCode 141)

Problem: Given a linked list head, return true if there's a cycle.

Why fast/slow fits: You need to check if following next pointers ever revisits a node. Hash set works but O(n) space. The interviewer says O(1) space. Floyd's algorithm is exactly this. Two pointers, no extra storage. If they meet, cycle confirmed. If fast hits null, no cycle.

Signal in the problem: "constant space", "detect loop", "does the list terminate".

Worked Example 2: Happy Number (LeetCode 202)

Problem: A happy number repeatedly replaces itself with the sum of the squares of its digits. Return true if it reaches 1, false if it loops forever.

Why fast/slow fits: This is an implicit cycle problem. Define f(n) as "sum of squares of digits of n". Starting from any number, the sequence n, f(n), f(f(n)), ... either terminates at 1 or enters a cycle. You don't have a linked list, but you have a function that maps state to next state. That's all Floyd's algorithm needs.

def is_happy(n: int) -> bool:
    def next_number(x: int) -> int:
        total = 0
        while x > 0:
            digit = x % 10
            total += digit * digit
            x //= 10
        return total

    slow = n
    fast = next_number(n)
    while fast != 1 and slow != fast:
        slow = next_number(slow)
        fast = next_number(next_number(fast))
    return fast == 1

The insight: if the number never reaches 1, it must eventually cycle (there are finitely many possible values before the sequence is forced to revisit one). Floyd detects that cycle. If they meet at 1, happy. If they meet anywhere else, not happy.

Signal in the problem: "eventually reaches", "repeat the process", "infinite loop vs termination".

The Common Mistake

The cycle comparison must use reference/pointer equality, not value equality. Two different nodes can have the same val. Comparing by value gives false positives on any list where duplicates exist, which is most real lists. Every implementation above uses the correct identity check for its language (is in Python, === in Kotlin/Swift, ReferenceEquals in C#, equal? in Ruby). This is the bug that causes wrong answers on submission while your local tests pass.

Also: initialize both pointers to head, not head.next for fast. Starting fast at head.next breaks the single-node self-loop edge case (next == self) depending on your loop condition.

Recap

Two pointers at the same start, one moves 1 step, one moves 2 steps
If fast hits null, no cycle; if they meet, cycle exists
The proof: once inside the cycle, the gap between them closes by 1 per step; a finite gap must reach 0
Time: O(n); space: O(1)
Works for any sequence with a "next state" function, not just linked lists
Always compare by identity (address/reference), never by value
The 2x speed ratio is conventional, clean, and gives the simplest Phase 2 math

Practicing fast/slow pointer problems is one of the spots where SpaceComplexity shines. The voice-based mock interviews cover exactly this class of problem and give rubric-based feedback on whether your explanation of the algorithm's correctness matches what an interviewer actually wants to hear.

For related pattern work, the dynamic programming framework is worth reading once you're comfortable with pointer tricks, since many DP problems on sequences share the same "one traversal" instinct.