Fast and Slow Pointers — Floyd's Cycle Detection, Cycle Start, Middle

Fast/slow pointers use two pointers at different speeds to detect cycles, find middles, or measure positions in linked lists — O(n) time, O(1) space.

Floyd's cycle detection (tortoise and hare)

• slow = head, fast = head
• Loop: slow = slow.next, fast = fast.next.next
• If fast or fast.next becomes null: no cycle
• If slow == fast: cycle detected

Why it works

• If no cycle: fast reaches end first
• If cycle: both eventually inside cycle; fast gains 1 on slow per iteration; gap becomes multiple of cycle length — they meet

Finding cycle start (second phase)

• After detection, reset one pointer to head
• Advance both at speed 1
• They meet at the cycle start

The math (why it works)

• L = distance head → cycle start

• C = cycle length

• D = distance cycle start → meeting point

• Slow traveled: L + D

• Fast traveled: L + D + kC (k extra laps)

• Fast = 2 × slow: 2(L + D) = L + D + kC

• So: L = kC - D

• Distance from head to start = distance from meeting point to start

• Walking both at speed 1 converges at start

Finding the middle of a linked list

• slow = head, fast = head
• slow = slow.next, fast = fast.next.next
• When fast reaches end: slow is at middle
• Even length: returns second middle (for first middle, start fast = head.next)

Kth node from end

• fast moves K steps first
• Then both move together until fast hits null
• slow is K from end
• O(n) single pass, O(1) space

Palindrome linked list

• Find middle with fast/slow
• Reverse second half
• Compare first half and reversed second half
• O(n) time, O(1) space
• Restore: re-reverse the second half if list must be preserved

Happy number (cycle detection on integer sequence)

• Sequence: n → sum of squares of digits
• If reaches 1: happy
• Else: cycle
• Apply Floyd's to the transformation function
• O(log n) per step, bounded iterations

Find duplicate in [1..n] array of length n+1

• Treat array as function f(i) = arr[i]
• Cycle must exist by pigeonhole
• Cycle start = the duplicate
• O(n) time, O(1) space (beats sorting or hashing)

Alternatives

HashSet method

• Track seen nodes/values in set
• O(n) time, O(n) space
• Simpler, but uses more memory
• First re-seen node = cycle start

Brent's algorithm

• Teleport slow pointer to fast at exponentially growing intervals
• ~36% fewer advances than Floyd's
• Less well-known
• Usually beyond interview scope

Edge cases

Empty list

• Return false / null

Single node, no cycle

• fast.next is null, loop exits, false

Single node, self-loop

• slow == fast after one step, true

Two nodes, cycle

• Correctly detected

Common pitfalls

1. NPE on fast.next.next

• Always check fast != null && fast.next != null before advancing

2. Confusing meeting point with cycle start

• They're different in general
• Need second phase to find cycle start

3. Not understanding the math

• Be ready to prove cycle start detection in interviews

4. Off-by-one in middle

• Even-length returns second middle by default
• Adjust initial fast pointer for first middle

5. Using wrong initial pointers

• Cycle start: start second pointer at head (not 'fast.next')

Advantages of Floyd's over HashSet

• O(1) space vs O(n)
• No allocation overhead
• Elegant, often interview-expected

When HashSet is fine

• You don't care about space
• You need to remember visited nodes for other purposes
• Code clarity matters more than memory efficiency

Recommendation: For cycle detection on linked lists, Floyd's algorithm is the expected interview answer — O(n) time, O(1) space. Memorize the two-phase cycle start detection: (1) slow/fast meet to detect the cycle; (2) reset one pointer to head, advance both at speed 1, they meet at the start. Be ready to prove the math (L = kC - D) because interviewers often ask why the second phase works. Know the middle-finding variant and its palindrome linked list application (find middle, reverse second half, compare) — both O(n) time, O(1) space. Know the Kth from end trick (fast starts K ahead, then both move together). Beyond linked lists, fast/slow detects cycles in any deterministic state transition: happy number (sum of squares of digits) and find duplicate in [1..n] array (treat array as function). The core insight: any repeating process with a 'next' function can be cycle-detected with fast/slow in O(1) space. For interviews, the HashSet alternative is acceptable but considered less elegant — use Floyd's when memory matters or for bonus points. Always handle edge cases (empty list, single node, self-loop) and check `fast != null && fast.next != null` before advancing to avoid NPE. The mental model: two pointers, one twice as fast; if they ever meet, there's a cycle; if fast hits null, there isn't. Simple, elegant, and applicable far beyond linked lists.