Clinic #34: Linked List Cycle

Pattern: Fast and slow pointers · LC 141 (and LC 142 in the second read)

Shows four problem shapes side by side. This clinic is the third one: a fast pointer lapping a slow one around a loop, worked on the problem it was made for.

Before you start. Linked Lists, Stacks & Queues built the chain: each item sits in a box called a node, and each node carries a note, the pointer, saying which node comes next. The only way through a chain is to start at the first node and follow the notes one at a time, because there is no “jump to box 5”. The last node’s note normally says “nothing next”, and that is how you know the chain ended.

The idea in 30 seconds

A linked list with a cycle has a note that points back to an earlier node, so walking it never ends.
Remembering every visited node (in a set) finds the loop, but its memory grows with the list.
Two pointers, slow moving one node and fast moving two, need only a fixed handful of variables however long the list.
No loop: the fast pointer reaches the end first. A loop: they must meet, because once both are going round it, the distance from fast to slow shrinks by exactly one each step and cannot skip zero.
To find the node where the loop begins, restart one pointer from the first node, move both one step at a time, and they meet there.
The method is credited to Floyd, but Wikipedia notes it is not in his published work; the attribution is disputed.

Read the story · Skip to the numbers