Cycle Detection

When a list stops ending

In a normal valid chain, repeatedly following next eventually reaches null. But if some node points to a node that was already encountered, a cycle appears and an ordinary traversal will never reach the end.

We could store every visited node in a set, but for a singly linked list there is a solution with O(1) additional space: Floyd's algorithm using fast and slow pointers.

Floyd's algorithm

Node slow = head;
Node fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
        return true;
    }
}

return false;

If there is no cycle, the fast pointer eventually reaches null. If a cycle exists, both pointers enter it. The fast pointer moves around the loop more quickly and eventually catches the slow one, so both references point to the same object.

Why references are compared

To detect a cycle, we must compare the nodes themselves with slow == fast, not their values. A list may contain different nodes with the same value — that does not mean the traversal has returned to a previously visited position.

Both pointers make a linear number of steps, so the running time is O(n), while the additional space remains O(1).