Cycle Detection — Floyd's Tortoise + Hare

Detect + find start

Node detectCycle(Node head) {
  Node slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
      Node a = head;
      while (a != slow) { a = a.next; slow = slow.next; }
      return a;
    }
  }
  return null;
}

Why it works

Let cycle start be at distance L from head, meeting at distance M into cycle. Slow moved L+M, fast moved 2(L+M) = L+M+kC. So M = kC - L. Restart from head → walk L → reach cycle start.

Cycle length

After first meet, keep slow, walk fast until they meet again. Number of steps = length.

Brent's algorithm

Alternative: track power-of-2 checkpoints. Fewer moves than Floyd, more comparisons. Similar bounds.