Pattern 03
Fast & Slow Pointers
Use either different speeds or a fixed gap to recover position information from a one-way chain.
Built from
Recognize it
Read the constraints before choosing the technique
Linked list with a cycle or middle
Indexing and length may be unavailable, but walkers can still encode position.
Nth item from the end in one pass
A fixed gap converts an end-relative position into simultaneous movement.
Repeated state in a deterministic process
Any state with exactly one successor forms a chain that either ends or cycles.
Constant extra space
The prompt is ruling out a visited-node set.
Cases that look similar but need another approach
The task needs to walk backwards
Two forward walkers cannot recover predecessor links.
Values, not positions, determine the answer
Fast and slow pointers derive information from movement, not magnitude.
Clarity matters more than extra memory
The set solution can be equally linear and may be easier to verify.
Reasoning
The ideas the code depends on
A node has no index
Moving means following next. The only safe way to know whether another hop exists is to check the current reference first.
Why two speeds detect a cycle
Inside a loop the fast walker gains one node per round on the slow walker. The gap cycles through a finite number of positions, so it must eventually become zero.
A fixed gap answers end-relative questions
Advance lead n times, then move lead and trail together. When lead reaches the end, trail remains exactly n positions behind.
Procedure
Turn the invariant into a repeatable process
- 01
Choose the relationship you need: two speeds for cycle or midpoint, fixed gap for distance from the end.
- 02
Initialize the walkers and establish that relationship.
- 03
Check every reference before following it.
- 04
Move the walkers without changing the intended speed or gap.
- 05
Interpret meeting, reaching null, or reaching the end according to the problem.
Common forms of the pattern
On a finite chain, fast reaches null or enters the loop. Inside a loop it closes the relative gap in at most one cycle length.
Implementation
Worked form
Linked-list cycle detection
Return true if repeatedly following next can revisit a node.
Linked-list cycle detection
boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
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 is fast:
return True
return Falsebool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}Common implementation mistakes
- Reading fast.next before proving fast is non-null
- Comparing node values instead of node identity for cycle detection
- Changing speed ratios partway through the loop
- Forgetting a dummy node when the head itself may be removed
Problem family
What stays the same—and what changes
These are not five unrelated solutions. Each problem preserves the movement rule and changes one part of the state or answer.
Middle of the Linked List
EasyReturn slow when fast reaches the end.
Happy Number
EasyTreat the digit transformation as the next link in a chain.
Palindrome Linked List
EasyFind the middle, reverse the second half, then compare halves.
Remove Nth Node From End
MediumUse the fixed-gap form, often with a dummy node.
Find Cycle Entry
MediumReset one walker after the first meeting.
Check yourself