Two runners on a track: if the track is a loop, the faster runner eventually laps the slower one; if it's a straight road, the fast one just reaches the end.
Clues that point here
→ Linked list cycle
→ Middle of a linked list
→ "Happy number" or any repeated sequence
→ Find the start of a cycle
→ O(1) space required for cycle detection
Not this pattern when
✕ You can use a HashSet and space isn't limited (simpler, same time)
✕ The structure supports random access (use indexes)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Fast and Slow Pointers · template
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
if (slow == fast) return true; // they met: there is a cycle
}
return false; // fast fell off the end: no cycle
// When the loop ends without a cycle, slow is at the middle.