Floyd's Cycle Detection: Tortoise and Hare in Python

By Engr. Henry Akpan

Detecting a Loop with Two Pointers

Imagine following a chain of links: each item points to the next. Either the chain ends, or at some point it loops back on itself and you would go round forever. How can a program tell which, using almost no memory? The elegant answer is Floyd's cycle detection algorithm, also called the "tortoise and hare": send two pointers along the chain, one moving one step at a time and the other two steps. If there is a loop, the fast one eventually laps the slow one and they meet. This tutorial explains why that works, how to find where the cycle starts and how long it is, and applies the method to linked lists, number sequences and the "find the duplicate number" problem, with Python code whose outputs were checked by running it.

Where Cycles Appear

  • A linked list whose last node mistakenly points back to an earlier node, so traversing it never ends.
  • Any function iterated on a finite set of values: x, f(x), f(f(x)), … must eventually repeat, because there are only finitely many values. Pseudo-random number generators, hash chains and "happy numbers" all behave like this.
  • An array where each value is an index of another position, which forms a hidden linked structure.

The simplest detector stores every visited item in a set and stops when one repeats. That works, but uses O(n) memory. Floyd's algorithm uses O(1).

The Tortoise and Hare

Start both pointers at the beginning. Each round, move the tortoise one step and the hare two steps.

  • If the hare reaches the end of the chain, there is no cycle.
  • If there is a cycle, both pointers eventually enter it. Once inside, the hare gains one step on the tortoise each round, so the gap between them shrinks by one each round until it becomes zero: they meet. This happens within one lap of the cycle after the tortoise enters it.

Floyd's Cycle Detection on a Linked List

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

def build(values, loop_to=None):
    """Build a linked list; if loop_to is an index, the last node points back to it."""
    nodes = [Node(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if loop_to is not None:
        nodes[-1].next = nodes[loop_to]
    return nodes[0]

def has_cycle(head):
    slow = 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

print(has_cycle(build([1, 2, 3, 4, 5])))
print(has_cycle(build([1, 2, 3, 4, 5], loop_to=2)))
print(has_cycle(build([7], loop_to=0)))

Output:

False
True
True

The check fast is not None and fast.next is not None protects against reaching the end of a list with no cycle. Comparing nodes with is checks that they are the same object, not just equal values.

Finding Where the Cycle Starts

After the pointers meet, there is a neat trick to find the first node of the cycle: move one pointer back to the head, then advance both one step at a time. The node where they meet again is the start of the cycle.

Why it works. Let the distance from the head to the cycle's start be μ, and the cycle length be λ. When they first meet, suppose the tortoise has taken k steps; the hare has taken 2k. The hare's extra k steps were whole laps of the cycle, so k is a multiple of λ. The tortoise is k − μ steps into the cycle. Walking a further μ steps would put it at k steps into the cycle, a whole number of laps, which is exactly the cycle start. Meanwhile a pointer starting from the head also reaches the cycle start after μ steps. So they arrive together.

def cycle_info(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None                      # no cycle

    # phase 2: find the start (mu steps from the head)
    mu, slow = 0, head
    while slow is not fast:
        slow, fast = slow.next, fast.next
        mu += 1

    # phase 3: measure the length by walking round once
    length, probe = 1, slow.next
    while probe is not slow:
        probe, length = probe.next, length + 1
    return slow.value, mu, length

print(cycle_info(build([10, 20, 30, 40, 50, 60], loop_to=2)))
print(cycle_info(build(list("abcdefgh"), loop_to=5)))
print(cycle_info(build([1, 2, 3])))

Output:

(30, 2, 4)
('f', 5, 3)
None

For the first list, the cycle starts at the node holding 30, two steps from the head, and contains 4 nodes (30, 40, 50, 60). The whole algorithm runs in O(μ + λ) time and O(1) memory.

Cycles in Number Sequences: Happy Numbers

A number is "happy" if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. Otherwise the sequence falls into a loop that never contains 1. The tortoise and hare work on any function, not just linked lists:

def digit_square_sum(n):
    return sum(int(d) ** 2 for d in str(n))

def is_happy(n):
    slow, fast = n, digit_square_sum(n)
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
    return fast == 1

print([n for n in range(1, 50) if is_happy(n)])

Output:

[1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49]

Unhappy numbers, such as 4, fall into the loop 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Find the Duplicate Number

A well-known interview question: an array holds n + 1 integers, each between 1 and n, so at least one value is repeated. Find a repeated value without changing the array and using only constant extra memory.

Treat each value as a pointer: from index i, go to index nums[i]. Because two positions hold the same value, two arrows point to the same index, which creates a cycle, and the duplicate value is exactly where the cycle starts. Floyd's algorithm finds it:

def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow

print(find_duplicate([1, 3, 4, 2, 2]))
print(find_duplicate([3, 1, 3, 4, 2]))
print(find_duplicate([2, 5, 9, 6, 9, 3, 8, 9, 7, 1]))

Output:

2
3
9

This runs in O(n) time with O(1) extra memory, without sorting or modifying the list, and works even when the duplicate appears several times.

Comparing Approaches

  • Visited set: simplest and finds the cycle start immediately, but uses O(n) memory.
  • Floyd's tortoise and hare: O(1) memory, finds the start and length with two extra passes.
  • Brent's algorithm: another O(1)-memory method that moves a single pointer and teleports a second one at powers of two; it usually calls the step function fewer times.

The same two-speed pointer idea also finds the middle of a linked list in one pass: when the fast pointer reaches the end, the slow one is halfway.

Summary

  • Floyd's cycle detection moves one pointer one step and another two steps; they meet only if there is a cycle.
  • To find the cycle start, reset one pointer to the head and move both one step at a time until they meet.
  • Walk once round the cycle from the meeting point to measure its length.
  • It uses O(1) memory and works on linked lists, iterated functions (happy numbers) and index arrays (find the duplicate).

Related Tutorials