Fast Slow Pointer

Intuition

Both pointer will move through the non-cycle part, then once inside the cycle, they have a relative speed of one for covering the gap between them so in “c” steps they will definitely meet.

When To Use

Use this for cycle detection, linked-list midpoint, or pointers moving at different speeds.

Template

slow = start
fast = start
 
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

Problems

Linked List Cycle

Problem: detect whether a linked list has a cycle.

Pattern: fast catches slow if a cycle exists.

Applied pseudocode:

slow = head
fast = head
 
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
 
    if slow == fast:
        return true
 
return false

Linked List Cycle II

Problem: return the node where the cycle begins.

When they meet, distance fromt he meeting point ( moving ahead ) to cycle start is same as distance from head to cycle start

A = distance off cycle
B = distance slow moves inside cycle
C = distance from meet to cycle start
 
Assume, fast completes JUST one full cycle to meet ( it can be k in general )
Cycle len = B + C
Fast dist = slow dist + cycle len
slow dist = A+B
fast dist = 2*(A+B)
 
with this you'll get A = C

Pattern: after meeting, move one pointer from head and one from meeting point.

Edge case: just one node list, easy to use a hasCycle bool

Middle of the Linked List

Problem: return the middle node.

Pattern: slow lands at middle when fast reaches the end.

Happy Number

Problem: detect a cycle in repeated digit-square sums.

Pattern: fast applies the transform twice per step.

Find the Duplicate Number

note that in this case duplicate can occur multiple times, the xor trick won’t work then

Problem: find duplicate in array values 1..n.

Pattern: treat values as next pointers and use cycle entry.