Detecting a linked-list cycle with fast and slow pointers

The problem

In a singly linked list, each node points to the next node or to null. An acyclic list eventually reaches null. A cyclic list has a link that points back to an earlier node, so following next references never ends.

The goal here is only to determine whether a cycle exists. The algorithm does not modify links or find the cycle’s entry point.

head -> [A] -> [B] -> [C] -> [D] -> [E]
                ^                    |
                |____________________|

Here, the tail points back to node B. A normal traversal would revisit B, C, D, and E forever.

Trace it

Use the controls below to step through both cyclic and acyclic lists. Watch each pointer position, then change the list shape to see how the stopping condition differs.

Move two pointers at different speeds

Floyd’s cycle-detection algorithm starts two references at the head:

• slow advances one link per iteration.
• fast advances two links per iteration.

If the list has no cycle, fast reaches null or the final node’s next is null. If there is a cycle, fast eventually catches slow inside it. Once both pointers are in the cycle, the gap between them shrinks by one node per iteration because fast gains one node on slow each time.

For the diagram above, the pointer positions are:

Both references now identify the same node, so the algorithm reports a cycle. It compares node identity, not stored values: two different nodes containing equal values are not a meeting.

Java implementation

The fast-pointer guard is important. It makes the two dereferences safe and identifies the acyclic case before either pointer advances beyond the list.

static final class Node<T> {
  final T value;
  Node<T> next;

  Node(T value) {
    this.value = value;
  }
}

static boolean hasCycle(Node<?> head) {
  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;
}

Java’s == compares the node references here, which is exactly what cycle detection requires. The method also handles an empty list and a one-node list without special cases.

Complexity and limits

The algorithm takes O(n) time and O(1) extra space, where n is the number of nodes visited before the pointers meet or the fast pointer reaches the end. It does not allocate a visited-node set, and it leaves every next reference unchanged.

This version answers only “does a cycle exist?” Finding the node where the cycle begins is a separate follow-up step.