Fast and Slow Pointers — How the Pattern Works
The Fast and Slow Pointers pattern (Floyd's Tortoise and Hare algorithm) traverses a linked structure or deterministic state-transition graph using two pointers advancing at a fixed 2:1 speed ratio: slow steps 1 link per iteration while fast steps 2 links. In an acyclic chain of length n, fast reaches the end after floor(n / 2) iterations, leaving slow positioned at the exact midpoint in a single pass. In a cyclic chain, once both pointers enter the cycle, fast reduces the modular backward gap to slow by 2 - 1 = 1 node per step, guaranteeing collision inside the cycle without skipping over slow and reducing O(n) hash-set space or multi-pass counting to O(n) time and O(1) auxiliary space.
- Singly or circular linked list problems asking to detect a cycle, compute cycle length, remove a cycle, or locate the middle node using
O(1)extra memory. - Symmetric linked list operations (palindrome check, maximum twin sum, list folding) where locating the midpoint enables reversing the second half in place.
- Implicit functional graphs where every state
xdeterministically maps to one next statef(x)(such as digit-square sums or modular jump arrays(i + nums[i]) % n), reducing state repetition to cycle detection. - Read-only array duplicate problems with
n + 1integers in[1, n], where treating values as next-index pointers (i -> nums[i]) maps the duplicate number to a cycle's entrance node.
- Dereferencing
fast.next.nextwithout guardingwhile fast and fast.next:first, causing a null-pointerAttributeErroron empty lists or odd/even list tails. - Comparing
slow.val == fast.valinstead of object identityslow is faston linked list nodes, which triggers false-positive collisions whenever distinct nodes hold equal values. - Misaligning the midpoint on even-length lists: starting
slow = fast = headstopsslowon the second middle node (index n // 2), whereas splitting into two disjoint lists requires stopping atindex (n // 2) - 1. - Accepting 1-node self-loops or mixed-direction edges in circular array problems instead of verifying
slow != step(slow)and uniform jump signs (sign * nums[x] > 0).
def detect_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return Nonedef reverse_second_half(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev, slow = slow, nxt
return prev