# 3.5 Cycle Detection

A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node. In such a structure, traversal never reaches `null`. Detecting this condition requires reasoning about the movement of pointers rather than counting nodes.

## Problem

Given the head of a singly linked list, determine whether the list contains a cycle. If a cycle exists, optionally identify the node where the cycle begins.

## Floyd’s Two-Pointer Method

The standard method uses two pointers that move at different speeds.

```text id="bq6p3c"
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
```

## Intuition

If the list has no cycle, `fast` reaches `null` and the loop terminates.

If a cycle exists, `fast` eventually laps `slow`. Since both pointers move within a finite loop, their positions must coincide after some number of steps.

## Invariant

At iteration `k`:

* `slow` has moved `k` steps
* `fast` has moved `2k` steps

The distance between them increases by one step per iteration inside the cycle, modulo the cycle length. This guarantees a meeting point.

## Detecting the Cycle Entry

After detecting a meeting point, the entry of the cycle can be found without extra memory.

Step 1: Run Floyd’s algorithm until `slow == fast`.

Step 2: Reset one pointer to the head.

```text id="o9cmu6"
ptr1 = head
ptr2 = slow

while ptr1 != ptr2:
  ptr1 = ptr1.next
  ptr2 = ptr2.next

return ptr1
```

## Why This Works

Let:

* `L` be the distance from head to cycle entry
* `C` be the cycle length
* `x` be the distance from entry to meeting point

At the meeting point:

```text id="8m4p9j"
2(L + x) = L + x + kC
```

which simplifies to:

```text id="7o1zcd"
L + x = kC
```

So:

```text id="gh4g4r"
L = kC - x
```

This means starting one pointer at head and one at the meeting point, both moving one step at a time, they meet exactly at the cycle entry.

## Complexity

| Operation    | Time | Space |
| ------------ | ---: | ----: |
| Detect cycle | O(n) |  O(1) |
| Find entry   | O(n) |  O(1) |

No additional memory is required.

## Alternative: Hash Set

A simpler but less efficient approach stores visited nodes.

```text id="0s9czt"
visited = set()

cur = head
while cur != null:
  if cur in visited:
    return true
  visited.add(cur)
  cur = cur.next

return false
```

This runs in O(n) time but uses O(n) space.

## Common Failure Modes

* Advancing `fast` without checking `fast.next`
* Comparing values instead of node identity
* Forgetting to handle empty or single-node lists
* Misplacing the reset step when finding the entry

## Key Insight

Cycle detection relies on relative motion. A single pointer cannot detect a cycle without memory. Two pointers with different speeds create a deterministic interaction inside a finite loop. Once they meet, the structure of distances reveals the entry point.

This technique extends beyond linked lists. It applies to functional graphs, repeated state transitions, and problems where the next state depends only on the current state.