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.

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.

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:

2(L + x) = L + x + kC

which simplifies to:

L + x = kC

So:

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

No additional memory is required.

Alternative: Hash Set

A simpler but less efficient approach stores visited nodes.

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.