Floyd's Cycle Detection — Tortoise and Hare Algorithm

You could detect a cycle with a hash set — store every node you visit, and if you see one again, there's a cycle. That works, but it uses O(n) space. Floyd's algorithm does it in O(1) space using two pointers moving at different speeds.

This isn't just a linked list trick. The same idea applies to any iterated function — detecting cycles in sequences, finding duplicate numbers in arrays, and more. The math behind it is worth understanding because it explains both why the pointers meet and how to find the cycle's start.

The Algorithm

Two pointers: slow (tortoise) moves one step at a time, fast (hare) moves two steps.

Detection: If there's a cycle, fast eventually laps slow and they meet inside the cycle. If there's no cycle, fast reaches the end (null). Finding the cycle start: After they meet, move one pointer back to the head. Now advance both at speed 1. They meet at the cycle's entry point.

Python — Cycle Detection in Linked List

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

JavaScript

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Finding the Cycle Start

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # found meeting point, now find entry
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

function detectCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

Why Does This Work?

This is the part most tutorials skip or hand-wave. Here's the actual math.

Let's define:

• L = distance from head to cycle start


• C = cycle length


• K = distance from cycle start to meeting point (within the cycle)

When slow enters the cycle (after L steps), fast has already traveled 2L steps, so fast is L steps into the cycle. That means fast is L mod C positions ahead of slow within the cycle.

For them to meet, fast needs to "catch up." Fast gains 1 step per iteration (speed 2 vs speed 1). The gap closes by 1 each step. They meet after the gap is covered.

At the meeting point, slow has traveled L + K steps. Fast has traveled 2(L + K) steps. The difference L + K must be a multiple of C:

L + K = nC    (for some integer n)
L = nC - K

Now reset slow to head. Both move at speed 1. Slow needs L steps to reach the cycle start. Fast, starting from the meeting point (which is K steps past the cycle start), needs L = nC - K steps. That means fast goes around the cycle n times and then backs up K positions from its current spot — landing exactly at the cycle start.

They meet at the cycle entry. That's why the two-phase algorithm works.

Finding Cycle Length

After detection (when slow and fast meet inside the cycle), keep one pointer still and advance the other until they meet again. The count is the cycle length.

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # measure cycle length
            length = 1
            current = slow.next
            while current != slow:
                length += 1
                current = current.next
            return length
    return 0

function cycleLength(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let length = 1;
      let current = slow.next;
      while (current !== slow) {
        length++;
        current = current.next;
      }
      return length;
    }
  }
  return 0;
}

Application: Find the Duplicate Number

LeetCode 287. Array of n+1 integers where each is in [1, n]. Exactly one duplicate exists. Find it without modifying the array and in O(1) space.

The insight: treat the array as a linked list where nums[i] is the next pointer. Index 0 is the head (since no value points to 0). A duplicate value means two indices point to the same "node" — that's a cycle. The duplicate is the cycle's entry point.

def find_duplicate(nums):
    slow = fast = 0
    # phase 1: detect cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

# phase 2: find entry
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

return slow

function findDuplicate(nums) {
  let slow = 0, fast = 0;
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

O(n) time, O(1) space. No sorting, no hash set, no modifying the array. This is probably the most elegant application of Floyd's algorithm.

Application: Happy Number

A number is "happy" if repeatedly summing the squares of its digits eventually reaches 1. If it doesn't, the sequence cycles. Use Floyd's to detect the cycle.

def is_happy(n):
    def next_num(num):
        total = 0
        while num > 0:
            num, digit = divmod(num, 10)
            total += digit * digit
        return total

slow = n
    fast = next_num(n)
    while fast != 1 and slow != fast:
        slow = next_num(slow)
        fast = next_num(next_num(fast))

return fast == 1

function isHappy(n) {
  function nextNum(num) {
    let total = 0;
    while (num > 0) {
      const digit = num % 10;
      total += digit * digit;
      num = Math.floor(num / 10);
    }
    return total;
  }

let slow = n;
  let fast = nextNum(n);
  while (fast !== 1 && slow !== fast) {
    slow = nextNum(slow);
    fast = nextNum(nextNum(fast));
  }
  return fast === 1;
}

Complexity

Operation	Time	Space
Cycle detection	O(n)	O(1)
Find cycle start	O(n)	O(1)
Find cycle length	O(n)	O(1)
Hash set approach	O(n)	O(n)

The O(1) space is the entire point. Everything else about Floyd's follows from that constraint.

When to Recognize This Pattern

• Linked list cycle problems (obviously)
• "Find the duplicate" with O(1) space constraint
• Any problem involving an iterated function where you need to detect periodicity
• Happy number, digit cycle problems
• Problems where a hash set solution exists but O(1) space is required

The signature: you have a sequence generated by repeatedly applying some function, and you need to know if it repeats. That's Floyd's territory.

Common Mistakes

Moving fast before checking for null. fast.next.next crashes if fast.next is null. Always check fast and fast.next in the while condition. Comparing values instead of references. In linked list problems, you compare node identity (slow == fast), not node values. Two different nodes can have the same value. Forgetting to use do-while for the duplicate number problem. Since slow and fast both start at 0, you need to move them at least once before checking equality. Use a do-while or move before the first comparison. Off-by-one in cycle length. Start counting at 1 (the meeting point itself), then advance until you return to it. The count equals the cycle length.

Build intuition for Floyd's by solving these problems on CodeUp — start with the basic linked list cycle, then tackle the duplicate number problem to really see the pattern's versatility.