Fast-Slow Pointer Technique

The fast-slow pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds.

slow = head
fast = head
while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next

When fast reaches the end, slow is at the middle. Why? Fast moves twice as fast, so it covers twice the distance in the same number of steps.

This technique solves three categories of problems:

$1.$ Finding the middle of a list

$2.$ Detecting cycles

$3.$ Finding the start of a cycle

All in $O(n)$ time and $O(1)$ space.