Fast and Slow Pointers

The third flavor of two pointers. Both pointers move forward through the same structure (a linked list, an array, or a cycle in a graph), but the fast pointer moves twice as fast as the slow one.

This sounds simple but unlocks three powerful tricks:

1. Cycle detection — if the fast pointer ever meets the slow one, there’s a cycle (Floyd’s tortoise and hare).
2. Linked-list midpoint — when the fast pointer reaches the end, the slow one is at the middle.
3. Finding the start of a cycle — after detection, reset one pointer to the head; advance both at the same speed; they meet at the cycle’s entry.

All three run in O(n) time and O(1) extra space — no hash set, no auxiliary array.

Trick 1 — Cycle detection

Given the head of a singly linked list, return true if there’s a cycle.

The brute force: store visited nodes in a hash set, check each new node. O(n) time, O(n) space.

Floyd’s: walk slow one step at a time, fast two steps at a time. If there’s a cycle, fast is gaining on slow by one node per step (relative speed = 1 within the cycle). It must eventually catch up. If there’s no cycle, fast runs off the end.

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

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

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Time: O(n). Space: O(1).

Trick 2 — Linked-list midpoint

Given the head of a linked list, return the middle node.

When fast runs off the end, slow is at the midpoint. For even-length lists, this returns the second of the two middle nodes (which is the LeetCode convention for “Middle of the Linked List”). To get the first of the two middles, start fast one node ahead.

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

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

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Time: O(n). Space: O(1).

The “find the middle in one pass” trick is the building block for Palindrome Linked List, Reorder List, and Sort List — anywhere you need to split the list in half cheaply.

Trick 3 — Finding the start of the cycle

Given a linked list with a cycle, return the node where the cycle begins.

After Floyd’s detection, reset one pointer to the head and advance both at the same speed. They meet at the cycle’s entry. This is one of those “math-magic” tricks that looks like sorcery the first time but is provable in three lines.

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // Phase 2: find the entry
            ListNode* p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;
        }
    }
    return nullptr;
}

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            p = head
            while p != slow:
                p = p.next
                slow = slow.next
            return p
    return None

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

Why it works (the math)

Let L = length from head to cycle entry. Let C = cycle length. Let m = distance from cycle entry to where slow and fast first met.

When they meet:

• slow has walked L + m steps.
• fast has walked 2(L + m) steps.
• fast has also walked L + m + kC steps for some positive integer k (it took k extra laps).

So 2(L + m) = L + m + kC, which gives L + m = kC, i.e. L = kC − m.

That means walking L steps from the head AND walking L steps from the meeting point both land at the same place — the cycle entry. So reset one pointer to head, walk both at speed 1, and where they meet is the start of the cycle.

Trick 4 — Find the Duplicate Number (sneaky cycle)

Given an array nums of n + 1 integers where each integer is between 1 and n (inclusive), there is at least one repeated number. Find it without modifying the array, in O(1) extra space.

The trick: treat the array as a linked list, where the “next” of index i is nums[i]. The duplicate creates a cycle, and the cycle’s entry is the duplicate. Floyd’s applies directly.

int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

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

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

O(n) time, O(1) space. The “obvious” O(n) time + O(n) space solution is a hash set; this version uses the cycle detection insight to achieve constant space.

When to reach for fast and slow

The general fast-slow pattern

The unifying observation: if iterating a function f from a starting point eventually loops, Floyd’s algorithm detects the loop in O(n) time and O(1) space. The function can be node.next (linked lists), nums[i] (array as a graph), or sum_of_squared_digits(n) (happy number). Anywhere you’d otherwise need a hash set to remember visited states, Floyd’s likely works in constant space.

Quick check

Next: advanced patterns — K-sum reduction, two-pointer merge, and the technique applied to two different arrays.