Fast/Slow Pointers (Floyd's Cycle Detection)
Two pointers moving at different speeds through a linked list or array: the fast pointer moves 2 steps per iteration, slow moves 1. If there's a cycle, they will meet.
Fast/slow = tortoise and hare on a circular track. If there's a loop, the hare laps the tortoise. No loop? The hare hits the finish line and the tortoise is at the halfway mark (linked list midpoint).
Cycle detection: fast and slow will meet inside the cycle if one exists. To find cycle start: after meeting, reset slow to head. Advance both by 1 step — they meet again at the cycle entry. Middle of linked list: when fast reaches end, slow is at middle (or middle-left for even-length). Palindrome linked list: find middle, reverse second half, compare. Happy number: apply cycle detection to the f(n) sequence.
Mathematical proof for cycle start: let F = distance from head to cycle entry, C = cycle length, K = distance from entry to where slow/fast meet. Slow pointer walked F + K steps; fast walked 2*(F+K). Fast has lapped slow m times: 2(F+K) = F + K + m*C → F + K = m*C → F = m*C - K. Resetting slow to head and both walking 1 step: after F steps, slow is at cycle entry; fast started K before entry and has walked F steps = m*C - K steps ahead, which is exactly at the entry (since m*C is full cycles). This proves the meeting point after reset is always the cycle entry.
Fast/slow pointers detect cycles in O(n) time and O(1) space — better than a hash set approach which is O(n) space. Beyond cycle detection, slow pointer at end gives middle of list — useful for palindrome checks and merge sort on linked lists. The mathematical derivation for finding the cycle start is elegant: after initial meeting, reset one pointer to head and advance both by 1; they meet at the cycle entry. I'd mention this is also applicable to 'duplicate number in array' problems where the array encodes a linked list.
The fast pointer must check both fast != null AND fast.next != null before advancing by 2. Checking only fast != null causes a null pointer exception on the second step when fast is at the last node of an odd-length list. Also: in the cycle start detection phase, both pointers must advance by EXACTLY 1 step — not fast by 2. Using 2 steps in the second phase gives incorrect results.