Skip to main content

Floyd's Linked List Cycle Finding

Given a linked list that may contain a cycle, detect the cycle and find its entry (node C where the loop begins).

Floyd’s cycle algorithm (tortoise and hare) does this in O(n) time and O(1) extra memory.

This lesson follows CP-Algorithms — Floyd’s cycle finding.

Related: Simulated Annealing (also uses a “ρ” / tortoise–hare idea in Pollard ρ — see Integer Factorization).

Phase 1 — Does a cycle exist?​

  • slow and fast both start at head.
  • Each step: slow = slow.next, fast = fast.next.next.
  • If they ever point to the same node → cycle.
  • If fast hits null → acyclic.
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Fast covers twice the distance of slow; the gap grows by 1 each iteration. Once both are in a cycle of length L, they meet after a finite number of steps (the lead is a multiple of L mod L).

Phase 2 — Where does the cycle start?​

After they meet at G inside the cycle:

  1. Reset slow = head (leave fast at G).
  2. Advance both one step at a time.
  3. Their next meeting point is C, the cycle entry.
// slow, fast already meet inside the cycle
slow = head;
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
}
return slow; // entry C

Why phase 2 works​

Let:

  • a = steps from head to C
  • b = steps from C to first meeting G
  • L = cycle length

At the first meeting:

slowDist = a + x L + b
fastDist = a + y L + b
fastDist = 2 · slowDist

⇒ a = (y − 2x) L − b

So walking a steps from head reaches C, and walking a steps from G (already b into the cycle) also wraps to C. Moving both one-by-one, they meet at the entry.

🧪 Tortoise & hare on an array “next” list

Check: Floyd cycle finding​

Quiz

Floyd cycle finding

1 / 4

In phase 1, fast moves…

Pick an answer to see if you are right.

Practice drills​

Activity: One tortoise step

next is given as a list (-1 = null). Input: i. Print next[i] (or -1 if i < 0).

Practice problems​

From CP-Algorithms / common LC mirrors:

Cheat sheet​

PhaseAction
1slow +1, fast +2 until equal or null
MeetProves a cycle; node is some G in the loop
2slow = head; both +1 until equal → entry C
Whya ≡ −b (mod L) from fast = 2·slow
CostO(n) time, O(1) memory