Cycle Detection in Linked Lists

Floyd's cycle detection algorithm, also known as the "tortoise and hare" algorithm, is a clever technique for detecting cycles in sequences using two pointers that move at different speeds.

The Core Concept

Imagine two runners on a circular track: one runs at normal speed (tortoise) and another runs twice as fast (hare). If the track is circular, the faster runner will eventually lap the slower one and they'll meet. If the track has an end, the faster runner will reach the finish line first.

This same principle applies to linked lists. We use two pointers:

• Slow pointer (tortoise): moves one step at a time
• Fast pointer (hare): moves two steps at a time

If there's a cycle in the linked list, the fast pointer will eventually "catch up" to the slow pointer inside the cycle. If there's no cycle, the fast pointer will reach the end of the list (null) first.

Why This Works

The mathematical reason this works is based on relative speed. Inside a cycle, the fast pointer gains one position on the slow pointer with each iteration. Since the cycle has finite length, the fast pointer will eventually close the gap and meet the slow pointer.

The algorithm is efficient because:

• Time Complexity: O(n) - we visit each node at most twice
• Space Complexity: O(1) - we only use two pointer variables

Key Advantages

• No extra memory needed (unlike marking visited nodes)
• Works on any sequence, not just linked lists
• Guaranteed to terminate in linear time