141 · Linked List Cycle

Two runners on the same track.

Two joggers start from the same trailhead — one at normal pace, the other at double speed. If the trail loops back on itself, the faster runner eventually laps the slower from behind. If the trail simply ends, the faster runner reaches the finish first. Floyd's algorithm applies the same intuition to a linked list: a slow pointer advances one node per step, a fast pointer advances two. Identical references prove a cycle; a null proves a finite chain. O(n) time. O(1) space.

Interactive

Watch slow and fast chase through the list

Concept

Tortoise, hare, and node identity

Cycle detection requires no extra memory. The key insight is that two pointers moving at different speeds must eventually collide inside any cycle — and that collision is about node references, not values.

Tortoise and hare

Slow moves one step per iteration, fast moves two. Inside a cycle of length C, the gap between them shrinks by exactly 1 each step. After at most C iterations inside the cycle, the gap reaches 0 and they occupy the same node.

speed difference of 1 guarantees convergence

Node identity

A cycle means the traversal revisits the same node reference — the same object in memory. Seeing the same value twice does not prove a cycle: different nodes may hold identical values. Tracking visited values in a hash set would produce false positives.

reference equality, not value equality

Meeting ≠ entry

When slow and fast meet, they share the same node reference — but that node is not necessarily the cycle's entry point. The meeting point lies somewhere inside the cycle, determined by the tail length and cycle length. Finding the exact entry requires a second pass (problem 142).

the meeting point is inside the cycle
Algorithm

Two pointers, one pass, constant space

The algorithm uses O(1) extra space — just two pointer variables. It makes at most O(n) steps before detecting a cycle or proving the list is acyclic.

  1. 1

    Initialize

    Set slow = head and fast = head. Both pointers start at the same node.

  2. 2

    Advance pointers

    While fast and fast.Next are not null: move slow = slow.Next (one step) and fast = fast.Next.Next (two steps).

  3. 3

    Check identity

    After each advance, compare slow and fast by reference. If they point to the same node object, a cycle exists — return true.

  4. 4

    Terminate

    If the loop exits because fast or fast.Next reached null, the list is acyclic — return false. A finite list always terminates the fast pointer.

Edge Cases

Degenerate inputs

The algorithm handles all boundary cases without special branches. The while-loop condition naturally covers empty lists, single nodes, and self-cycles.

Empty list

When head is null, there are no nodes to traverse. The while condition fails immediately. Return false.

Self-cycle

A single node whose .Next points to itself. After one advance, both slow and fast land on the same node — cycle detected in a single step. Try the "self-cycle" preset.

Duplicate values ≠ cycle

A list like [1, 2, 1] with no cycle contains the value 1 at two different nodes. Comparing values would falsely report a cycle. Floyd's algorithm compares node references, not values, so it correctly returns false.