Linked Lists6 min read

Floyd's Cycle Detection

Catch a loop in a linked list using just two pointers and no extra memory

time: \(O(n)\)space: \(O(1)\)

Imagine two runners on a circular track. One runs at normal speed, the other runs twice as fast. If they start together, will the fast runner ever lap the slow one and meet them again? Yes — always, and relatively quickly.

Now imagine the track is a linked list with a cycle (a loop in the chain). A slow pointer moves one node at a time. A fast pointer moves two nodes at a time. If a cycle exists, the fast pointer will eventually lap the slow pointer and they will point to the same node. If there's no cycle, the fast pointer will reach the end of the list (null) first.

This is Floyd's Cycle Detection Algorithm — also called the tortoise and the hare. It solves a problem that sounds expensive in \(O(1)\) space, with no hash sets, no visited arrays, nothing but two pointer variables.

◈ Watch cycle detection

← → arrow keys to step · click elements to interact

Floyd's Cycle Detection

class Node:
    def __init__(self, val): self.val = val; self.next = None

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

# Build: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node 2)
nodes = [Node(i) for i in [1,2,3,4]]
for i in range(3): nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # create cycle

print(has_cycle(nodes[0]))  # True

# No cycle
linear = [Node(i) for i in [1,2,3]]
for i in range(2): linear[i].next = linear[i+1]
print(has_cycle(linear[0]))  # False

Output

True
False

Phase 1: Does a cycle exist?

pseudocode

slow = head
fast = head
while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True  # cycle detected
return False  # no cycle

Why does this work? If there's a cycle of length k, the fast pointer enters the cycle and laps the slow pointer. The gap between them closes by 1 each step (fast gains 1 node per step on slow), so they must meet within k steps after both enter the cycle. Total steps: \(O(n)\).

Phase 2: Where does the cycle start?

Once you've detected the meeting point, you can find the exact node where the cycle begins with a elegant mathematical trick:

Keep one pointer at the meeting point.
Move the other pointer back to head.
Advance both pointers one step at a time.
Where they meet is the start of the cycle.

Why? Let F = distance from head to cycle start, a = distance from cycle start to meeting point (inside cycle), C = cycle length. At the meeting point, slow has traveled F + a steps. Fast has traveled F + a + nC (full extra laps). Since fast moves twice as fast: 2(F + a) = F + a + nC, which simplifies to F = nC − a. Moving one pointer from head and one from the meeting point at the same speed, they both arrive at the cycle start after exactly F steps.

Note: The key insight is mathematical: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (modulo full laps). This elegant relationship means the two-pointer reset always finds the cycle entry in \(O(n)\) total time.

Why not use a hash set instead?

You could detect a cycle by storing every visited node in a hash set and checking if you've seen the current node before. That works, but costs \(O(n)\) extra space. Floyd's algorithm solves the same problem with \(O(1)\) space — just two pointer variables. For large lists, this is a meaningful difference.

Where does this appear in practice?

Interview problems — LeetCode 141 (has cycle) and 142 (find cycle start) are classic problems directly using this algorithm.
Detecting infinite loops in custom iterators or generators.
Finding the duplicate number — a clever problem (LeetCode 287) models an array as a linked list and applies Floyd's to find the repeated value in \(O(n)\) time, \(O(1)\) space.
Rho algorithm for integer factorization uses the same cycle-detection idea.

Complexity

Cycle detection (Phase 1)Fast pointer laps slow within n steps

Fast\(O(n)\)

Find cycle start (Phase 2)One more pass of at most F steps

Fast\(O(n)\)

SpaceOnly two pointer variables ever

Constant\(O(1)\)

Find Cycle Start (Entry Point)

class Node:
    def __init__(self, val): self.val = val; self.next = None

def find_cycle_start(head):
    slow = fast = head
    # Phase 1: detect cycle
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow is fast: break
    else:
        return None  # no cycle
    # Phase 2: find entry
    slow = head
    while slow is not fast:
        slow = slow.next; fast = fast.next
    return slow.val

nodes = [Node(i) for i in [1,2,3,4,5]]
for i in range(4): nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle enters at node with val=3
print(find_cycle_start(nodes[0]))  # 3

Output

Challenge

Quick check

In Floyd's cycle detection, the slow pointer moves 1 step and the fast pointer moves 2 steps per iteration. If there is NO cycle, what happens?

Singly Linked List

A chain of boxes — each one knows only where the next box is

→

Reversing a Linked List

Flip the entire chain so the last node becomes first — iteratively or recursively

→