← All patterns

Fast and Slow Pointers

Floyd's tortoise-and-hare. Speed-2 vs speed-1 pointers detect cycles, find midpoints, and solve linked-list-as-functional-graph problems in O(1) extra space. The atomic cycle-detection primitive.

10 problems 4 Easy 6 Medium

Floyd's tortoise-and-hare detects cycles in any sequence governed by a deterministic step function. The 'fast' pointer moves twice as fast as the 'slow' one; inside any cycle their gap closes by 1 per step, guaranteeing a meeting within at most one full lap. The distance-lemma extension (advance one pointer from the head and the other from the meeting point at speed 1) lands both at the cycle entry.

The technique extends well beyond linked lists: any 'array as functional graph' (find-the-duplicate, happy number) or 'find the middle' problem on a singly-linked structure uses the same primitive.

When to reach for this pattern

  • Linked list with a possible cycle, or a guarantee that one exists
  • Find the middle or kth-from-end of a linked list
  • Sequence with a deterministic step function (numerical iteration, array indices as edges)
  • Palindromic check on a linked list
  • Pigeonhole-style 'one duplicate in [1..n]' problems on an array

Canonical template 

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) {
        // cycle exists. Reset one pointer to head; they meet at the entry.
        ListNode* p = head;
        while (p != slow) { p = p->next; slow = slow->next; }
        return p;
    }
}
return nullptr;

C++ · adapt the names and types to your problem.

Common pitfalls

  • Dereferencing fast->next->next without first checking fast->next — null deref
  • Starting both pointers offset (e.g. slow = head, fast = head->next) breaks the entry-finding lemma
  • On numerical step functions, forgetting the answer is at the cycle entry, not where the pointers first meet
  • Even/odd length: pick the convention for 'middle of even-length list' (first vs second middle) before coding

Related patterns

Two Pointers In-Place Linked List Cyclic Sort

Problems (10)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.