Fast & Slow Pointers
Move one pointer at twice the speed of the other. They meet only inside a cycle, and when the fast one ends the slow one sits at the middle.
Linked ListO(n) time, O(1) spaceNew9 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
cycle detection
middle of the list
nth node from the end
happy number
The template
Get this into muscle memory, then adapt the condition per problem.
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
} Watch Floyd Cycle DetectionIf you are stuck
The generic hint ladder for this pattern, in order.
- 1You are told not to use extra memory, so a visited set is out.
- 2Two runners on a circular track always meet.
- 3To find the cycle start, reset one pointer to head and step both one at a time.
Drill it
Every problem in the bank that uses this pattern.
0 / 9 solved