DSAMonth 1 · Week 3

Day 14: Fast & Slow Pointers (Cycle Detection)

Use Floyd's Tortoise and Hare to detect and locate cycles in linked lists (and equivalent problems) in O(n) time and O(1) space.

Mark this day complete

Study

Concepts

Two runners at different speeds must meet in a cycle

Move a `slow` pointer one step at a time and a `fast` pointer two steps at a time through a linked structure. If there is no cycle, `fast` reaches the end (null) first. If there IS a cycle, `fast` eventually laps `slow` from behind and they land on the exact same node — this is mathematically guaranteed because the gap between them shrinks by exactly one node per iteration once both are inside the cycle.

Finding the cycle's STARTING node is a second phase: once slow and fast meet, reset one pointer to the head and advance both one step at a time — they meet again exactly at the cycle's entry point. This follows directly from the distance relationships in Floyd's algorithm (provable, but usually just memorized for interviews).

See It

Visualizations

Visualization

Floyd's cycle detection — two phases

Phase 1: detect

slow +1, fast +2 per step — if they meet, a cycle exists

Meeting point found

both pointers now share a node inside the cycle

Phase 2: locate start

reset one pointer to head, advance both +1 — they meet at the cycle entry

Build It

Code Examples

Detect a cycle in a linked list

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

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // they lapped — cycle confirmed
  }
  return false; // fast hit the end — no cycle
}

Find the node where the cycle begins

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

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Phase 2: reset one pointer to head, advance both by 1
      let ptr = head;
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr; // the cycle's entry node
    }
  }
  return null; // no cycle
}

The same trick outside linked lists: "Happy Number"

function isHappy(n) {
  const next = (x) =>
    String(x)
      .split('')
      .reduce((sum, d) => sum + Number(d) ** 2, 0);

  let slow = n;
  let fast = next(n);

  while (fast !== 1 && slow !== fast) {
    slow = next(slow);
    fast = next(next(fast));
  }
  return fast === 1; // reached 1 -> happy; met slow before 1 -> stuck in a cycle
}

console.log(isHappy(19)); // true

Remember

Key Takeaways

slow +1 / fast +2 per step is the whole algorithm — memorize the movement rule, not just the name.
If fast reaches null, there is no cycle — that is the O(n), O(1)-space termination condition.
Meeting point ≠ cycle start — finding the start needs the second reset-and-walk phase.
The same pattern applies to any "sequence that might loop forever" problem, not just linked lists (e.g. Happy Number).
This is the O(1)-space alternative to using a Set of visited nodes (which works but costs O(n) space).

Do It

Practice

1Implement hasCycle using a Set of visited nodes first (O(n) space), then convert it to Floyd's O(1)-space version.
2Solve "Find the Duplicate Number" in an array using the fast/slow pointer trick, treating array values as "next pointers".
3Explain in writing why the gap between slow and fast shrinks by exactly 1 per step once both are inside the cycle.