How do you detect a cycle with Floyd's tortoise and hare?

Question

Accepted Answer

**Floyd's cycle detection** finds a loop in a sequence (like a linked list) using two pointers moving at different speeds. If a cycle exists, the fast pointer eventually laps and meets the slow one. It uses **O(1)** extra space.

## The idea

Move a **slow** pointer one step and a **fast** pointer two steps. In a cycle, the gap shrinks by one each step, so they must collide; without a cycle, fast reaches the end.

## Example

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## Complexity

- **Time:** O(n). **Space:** O(1).

A hash-set approach also works but costs O(n) space; Floyd's uses constant space.

## When to use / pitfalls

Use for **linked-list loop detection**, finding the cycle's start, and detecting cycles in functional graphs (each node has one successor). Always guard `fast.next` to avoid null dereferences. For general graphs, use DFS with a recursion stack instead.

## Why it matters

Detecting cycles is essential for safe traversal — an undetected loop means infinite iteration.

Floyd's algorithm is a beautiful example of solving an O(n)-space problem in O(1) space with a clever invariant.

It appears in linked-list interviews and in detecting infinite loops in state machines and number sequences.