Cycle Detection

A cycle in a linked list means some node’s next pointer leads back to an earlier node, creating an infinite loop. Detecting this naively (storing every visited node in a Set) works but costs O(n) extra space. Floyd’s algorithm uses only two pointers and O(1) space.

Node Class

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

Step 1 — Detect a Cycle

Move slow one step at a time and fast two steps at a time. If they ever point to the same node, there is a cycle.

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;   // pointers met inside cycle
  }

  return false;  // fast reached the end — no cycle
}

Why They Always Meet

Imagine the list has a non-cyclic prefix of length F followed by a cycle of length C. Once both pointers enter the cycle, fast gains one step on slow every iteration. The gap between them decreases by 1 each round until it becomes 0 — they must meet within at most C more steps. No matter how large the list, the meeting is guaranteed.

Step 2 — Find the Cycle Entry Node

After detection (when slow === fast), reset one pointer to head. Advance both pointers one step at a time. They will meet exactly at the cycle entry node.

function detectCycleStart(head) {
  let slow = head;
  let fast = head;

  // Phase 1: detect
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (fast === null || fast.next === null) return null;  // no cycle

  // Phase 2: find entry
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;  // cycle entry node
}

The math behind Phase 2: at the meeting point, slow has traveled F + a steps where a is its distance inside the cycle. Resetting one pointer to head and advancing both at the same speed means they rendezvous after exactly F more steps — which lands them at the cycle entry.

Building a Test Case

// Build list 0 → 1 → 2 → 3 → 4 → (back to node at index 2)
const nodes = [0, 1, 2, 3, 4].map(v => new ListNode(v));
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[4].next = nodes[2];  // cycle here

console.log(hasCycle(nodes[0]));                   // true
console.log(detectCycleStart(nodes[0]).val);       // 2

Complexity

Up Next

The same two-pointer speed trick finds the middle node of a linked list — useful for palindrome checks and merge-sort splits.