Cycle Detection with Fast-Slow

If there's a cycle, fast and slow pointers will eventually meet inside the cycle.

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

Why do they meet? Once both pointers enter the cycle, fast gains one position on slow each step. Since the cycle has finite length, fast will eventually catch up.

If there's no cycle, fast reaches the end and the loop exits normally.

Time: $O(n)$. Space: $O(1)$.

You've implemented Floyd's cycle detection algorithm, one of the most famous algorithms in computer science.