Fast and Slow Pointers: Floyd's Cycle Detection

The Problem: Detecting a Cycle in $O(1)$ Space

Consider LeetCode 141: you have a linked list, and it might contain a cycle, where some node's next pointer leads back to an earlier node, creating an infinite loop. You need to determine whether a cycle exists. The obvious approach is to use a hash set to track every node you visit, but that costs $O(n)$ space. Can you do it in $O(1)$ space?

The answer is Floyd's tortoise and hare algorithm, one of the most elegant ideas in computer science.

The Fast-Slow Pointer Idea

Initialize two pointers at the head of the list. The slow pointer moves one step at a time. The fast pointer moves two steps at a time. If there is no cycle, the fast pointer will reach the end of the list (null) and you can return false. If there is a cycle, both pointers will eventually enter the cycle, and the fast pointer will catch up to the slow pointer from behind, and they will meet at some node inside the cycle.

Why They Must Meet

Once both pointers are inside the cycle, think about the gap between them. Each step, slow advances 1 node and fast advances 2 nodes, so the distance between fast and slow (measured around the cycle) decreases by exactly 1 per step. If the gap starts at d, it becomes d-1, then d-2, and so on until it reaches 0. They must meet. There is no way for fast to "jump over" slow, because the gap shrinks by exactly 1 each step.

A Concrete Example

Consider a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (back to node 3, forming a cycle).

• Step 0: slow = 1, fast = 1.
• Step 1: slow = 2, fast = 3.
• Step 2: slow = 3, fast = 5.
• Step 3: slow = 4, fast = 4. They meet at node 4. Cycle detected.

Here is the code for simple cycle detection:

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

Finding the Cycle Start: Floyd's Algorithm Phase 2

LeetCode 142 takes this further: detecting a cycle is useful, but you need to know where the cycle begins. Floyd's algorithm has a second phase that finds this. After the slow and fast pointers meet inside the cycle, reset the slow pointer back to the head of the list. Now move both pointers one step at a time. The node where they meet again is the start of the cycle.

The Mathematical Proof

Let F be the distance from the head to the cycle entrance, C be the cycle length, and a be the distance from the cycle entrance to the meeting point (measured in the direction of traversal).

When slow and fast meet, slow has traveled F + a steps. Fast has traveled 2(F + a) steps (since it moves twice as fast). The difference F + a must be a multiple of the cycle length C, because fast made some extra full loops around the cycle. So F + a = kC for some integer k.

Now reset slow to the head. Both pointers move one step at a time. Slow needs F steps to reach the cycle entrance. Meanwhile, fast starts at the meeting point (which is a steps past the cycle entrance) and takes F steps. Its position within the cycle becomes a + F, and since a + F = kC, that puts it exactly at the cycle entrance. They meet at the cycle start.

Here is the complete code:

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Phase 2: find the entrance
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow  # cycle start
    return None

Find the Duplicate Number: The Array-as-Linked-List Trick

LeetCode 287, Find the Duplicate Number, is a brilliant application of Floyd's algorithm to an array problem. You are given an array nums of length n + 1 containing integers in the range [1, n]. Exactly one number is duplicated (possibly more than once). Find it in $O(1)$ space without modifying the array.

The trick is to reinterpret the array as an implicit linked list. Treat each index i as a node, and nums[i] as the "next pointer," the index of the next node. Since all values are in range [1, n] and there are n + 1 entries, index 0 is a valid starting point that no value points back to (values are at least 1). The duplicated value means two different indices point to the same "next node," which creates a cycle in this implicit linked list. The entrance to the cycle is the duplicate number.

Let us trace through [1, 3, 4, 2, 2]:

• The implicit edges are: 0->1, 1->3, 2->4, 3->2, 4->2. Written as a chain starting from 0: 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> 2 ... There is a cycle: 2 -> 4 -> 2. The cycle entrance is node 2, and nums[2] = 4... but actually let us be more careful. The duplicate value is 2. Both index 3 and index 4 point to index 2. So the cycle entrance is index 2, and the duplicate is the value 2, which is the index that has two incoming edges.

Running Floyd's algorithm: start at index 0.

• Phase 1 (find meeting point): slow follows nums[slow], fast follows nums[nums[fast]].
• Phase 2 (find entrance): reset one pointer to 0, advance both by one. They meet at the cycle entrance, which is the duplicate.

def find_duplicate(nums):
    # Phase 1: find intersection
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: find entrance
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Finding the Middle of a Linked List

LeetCode 876 demonstrates a beautifully simple application of the fast-slow pointer technique beyond cycle detection: finding the middle node of a linked list in one pass. Move slow by 1 and fast by 2. When fast reaches the end of the list (or the node before the end), slow is at the middle.

Why? Fast travels at double speed, so when fast has traversed the entire list, slow has traversed exactly half. For even-length lists, this gives you the second of the two middle nodes (which is the conventional choice for most problems).

def middle_of_list(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Linked List Palindrome Check

In LeetCode 234, checking whether a linked list is a palindrome combines multiple techniques. First, use fast-slow pointers to find the middle. Then reverse the second half of the list in place. Finally, compare the first half and the reversed second half node by node.

def is_palindrome(head):
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt
    # Compare halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

This runs in $O(n)$ time and $O(1)$ space. The only downside is that it modifies the list (reversing the second half), though you can reverse it back afterward if the problem requires preserving the original structure.

Complexity Analysis

All variations of the fast-slow pointer technique run in $O(n)$ time, where $n$ is the number of nodes in the list (or the size of the array, for the duplicate number problem). The space complexity is $O(1)$: you only ever maintain two pointers regardless of input size.

The key insight across all these problems is the same: by moving two pointers at different speeds, you extract structural information about the sequence, whether it loops, where the midpoint is, or where a duplicate hides, without needing any extra data structures.

Recognizing this pattern

You're probably looking at fast-slow pointers when:

• You need to detect a cycle in a linked list or a functional iteration x = f(x).
• You need the middle of a linked list in one pass without knowing the length.
• You must find a duplicate in an array of $n+1$ integers drawn from $[1..n]$ without modifying the input and in $O(1)$ extra space.
• You want to identify the start of a cycle, or detect a property (like a happy number) by checking whether the sequence eventually loops.

Common templates:

• Floyd's cycle detection: slow moves one step, fast moves two; they meet iff there is a cycle. Example: Linked List Cycle.
• Cycle entry point: after detection, reset one pointer to head and advance both one step until they meet. Example: Linked List Cycle II.
• Midpoint in one pass: fast moves two steps, slow lands on the middle when fast hits the end. Example: Middle of the Linked List.
• Duplicate via index-as-pointer: treat nums[i] as the next index, then run Floyd. Example: Find the Duplicate Number.
• Functional-graph loop check: repeat x = f(x) with two speeds to detect convergence or cycle. Example: Happy Number.