Linked List Cycle

EasyLinked ListLinked ListTwo PointersHash Table

Problem

You are given the head of a singly linked list. Determine whether it contains a cycle: whether some node's next pointer eventually loops back to an earlier node instead of ending at nothing.

Example. A list where the last node's next points back to the second node forms a cycle and should report true; an ordinary list that ends normally should report false.

Key idea

The direct approach keeps a set of every node visited and checks each new node against it; the moment a node repeats, a cycle exists. That works but costs memory proportional to list length. The classic improvement avoids extra storage by moving two pointers at different speeds: one step at a time for a slow pointer, two at a time for a fast one.

If the list has no cycle, the fast pointer simply reaches the end first. If a cycle does exist, both pointers eventually enter it and can never leave, and because the fast pointer gains one extra step on the slow pointer every iteration, it cannot jump over it: it is forced to land on the same node within one full loop of the cycle. That guaranteed meeting is the signal that a cycle is present.

Solution

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next; // one step
    fast = fast.next.next; // two steps
    if (slow === fast) {
      return true; // fast lapped slow, which can only happen inside a cycle
    }
  }

  return false;
}

Complexity

  • Time: O(n). Each pointer traverses at most a small multiple of the list length before finishing or meeting.
  • Space: O(1) with the two-pointer approach; O(n) if a hash set of visited nodes is used instead.

Watch out for

  • Advance the fast pointer only after confirming both it and its next node are non-null, or the traversal crashes on a list without a cycle.
  • A meeting of the two pointers only confirms a cycle exists; finding where the cycle begins requires an additional phase not needed here.
  • A list of zero or one node terminates cleanly without ever meeting, so no special-casing is needed for short lists.

Pattern

This is Floyd's tortoise-and-hare technique, the standard fast/slow pointer pattern for cycle detection. The same mechanics locate a list's middle node in one pass and can even apply to an array reinterpreted as an implicit linked list, as in Find the Duplicate Number.

Related questions