Floyd's Tortoise & Hare

The shape of the problem

Detect whether a linked list contains a cycle. If it does, locate the node where the cycle begins. Solve in O(1) extra memory.

The naive approach uses a hash set: walk the list, insert each node into the set, return the first node already present. O(n) time, O(n) memory. Floyd's algorithm achieves the same result with O(1) memory by exploiting the fact that two pointers moving at different speeds inside a cycle must eventually meet.

Detection, why fast laps slow

Suppose the list has a cycle. Both pointers eventually enter it (fast first, but they both arrive). Once both are inside the cycle, the gap between them changes by exactly one node per iteration: fast moves two, slow moves one, so fast gains one. The cycle has finite length L. After at most L iterations of both being inside the cycle, fast has gained L positions on slow, closing the gap to zero. They meet.

If there is no cycle, fast eventually reaches null (it's strictly faster, so it hits the end first). The loop terminates without a meeting.

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

The condition fast is not None and fast.next is not None is the no-cycle escape hatch. If fast.next were null, fast.next.next would crash. We check both before each two-step.

Locating the cycle's start, the modular identity

The detection above tells us a cycle exists. Now we want the entry point, the first node that lies on the cycle.

Set up the variables:

• μ = number of nodes from the head to the cycle's start (the "tail length"). If the cycle starts immediately, μ = 0.
• L = length of the cycle.
• k = position of the meeting node within the cycle, measured forward from the cycle's entry. So 0 ≤ k < L.

At the meeting moment, slow has taken μ + k steps. Fast has taken 2(μ + k) steps. Fast also walked μ steps to enter the cycle, then went around it some number of times m ≥ 1 before reaching position k. So fast's total is μ + m·L + k. Equating:

2(μ + k) = μ + m·L + k
       μ + k = m·L
       μ = m·L − k
       μ ≡ −k  (mod L)
       μ ≡ L − k  (mod L)

The last line is the key identity: the distance from the head to the cycle's start equals the distance from the meeting point forward to the cycle's start, modulo L.

So if we restart one pointer at the head and let both pointers advance one step at a time, after exactly μ steps:

• The pointer that started at the head has walked μ steps and now sits at the cycle's entry.
• The pointer that started at the meeting point has walked μ steps too, and by the identity, μ ≡ L − k (mod L), which lands it at the cycle's entry.

They meet at the cycle's entry. That's the algorithm.

def find_cycle_start(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:
            break
    else:
        return None                  # no cycle (Python's for-else / while-else)

    # Restart slow at head; advance both one step at a time.
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow                      # the cycle's entry point

A worked trace

Consider a list 1 → 2 → 3 → 4 → 5 → 6 → 3 (back to 3). So μ = 2, L = 4, the cycle is 3 → 4 → 5 → 6 → 3.

iter   slow   fast
  0    1      1
  1    2      3
  2    3      5
  3    4      3   (fast went 5→6→3)
  4    5      5   ← meet at 5

So k = 2 (position of node 5 within the cycle, with 3 = position 0).
Identity: μ = 2, L − k = 4 − 2 = 2. ✓

Restart slow at head:
iter   slow   fast
  0    1      5
  1    2      6
  2    3      3   ← meet at 3 - the cycle's entry

The math holds. The proof is exact, and the algorithm runs in O(n) time with three pointer variables.

Implicit graphs. Find the Duplicate Number

The technique extends past linked lists. Consider an array of n+1 integers where each element is in [1, n]. By the pigeonhole principle, at least one value appears twice. Find that value in O(n) time and O(1) memory, without modifying the array.

Treat the array as a function i → a[i]. Starting at index 0 and repeatedly applying this function defines a sequence, and the duplicate value forces a cycle in that sequence. Floyd's algorithm applied to this implicit graph finds the cycle's entry, which is exactly the duplicated value.

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 = nums[slow]
        fast = nums[fast]
    return slow

Why this works: the duplicate value is reached by two distinct index paths, so traversing i → nums[i] from index 0 must eventually visit the duplicate from "above" (the other path), creating a cycle whose entry is the duplicated value. The Floyd machinery is identical; only the "next" function changed.

Complexity, reasoned

Detection: O(n), fast traverses at most 2n nodes before either meeting slow or reaching the end. Memory: O(1). Locating the cycle's start: an additional O(n), slow walks at most n more steps. Total: O(n) time, O(1) memory. The hash-set version is also O(n) time but O(n) memory; Floyd's wins on memory by a factor of n.

When to use Floyd over a hash set

Always, if memory is constrained, embedded systems, large lists, streaming data. The hash-set version is slightly faster in raw wall-clock time on small inputs (no swap with the cache), but the memory savings dominate at scale. The exception: if you also need to identify which nodes lie on the cycle and how many, the hash set gives you that information for free; Floyd's tells you only the entry.

Where beginners go wrong

• Skipping the null guard. Without fast is not None and fast.next is not None, the no-cycle case crashes on the first dereference of a null. Both checks are required.
• Restarting the wrong pointer. The identity says μ ≡ L − k (mod L). It's slow that goes back to the head; fast stays at the meeting point. Reversing them gives wrong answers (sometimes, only when the random arithmetic happens to align).
• Using == when you want identity. In Python, slow is fast compares object identity (correct here, we want "the same node"). slow == fast may compare values, which can return True for two different nodes with equal payloads. The "is" version is the one that means what we want.
• Trying to detect cycles by counting nodes. "If I've walked more than n nodes, there must be a cycle." This is correct but requires knowing n in advance and uses O(1) memory only by accident, it's the same memory as Floyd's but reaches the answer slowly and gives no information about the cycle's structure.
• Confusing the algorithm with Brent's. Brent's cycle detection is a different O(n)-time, O(1)-memory algorithm with smaller constants. Both work; Floyd's is more famous and more often expected in interviews.

What to read next

The In-Place Reversal Patterns deep-dive complements this one, both are pointer-discipline classics that show up in linked-list interviews. The Two Pointers module formalises fast/slow pointers as a transferable shape that goes well beyond linked lists.