Pointer Chasing: Floyd's Tortoise-and-Hare vs Brent's Cycle Detection

The $\rho$ (Rho) Topology & Floyd's Modular Congruence Proof

Consider a singly linked list (or iterated function $x_{i+1} = f(x_i)$ in Pollard's rho integer factorization and PRNG period testing) that has a non-cyclic prefix (tail) of $\mu$ edges leading to a cycle entrance node $E$, followed by a directed cycle of $\lambda$ edges. In Floyd's Cycle-Finding Algorithm (attributed to Robert W. Floyd, 1967, in Knuth TAOCP Vol. 2), a slow pointer $T$ (Tortoise) advances 1 step per iteration ($t_k = k$) and a fast pointer $H$ (Hare) advances 2 steps per iteration ($h_k = 2k$):

• Phase 1 (Cycle Detection & Meeting Point): Once $k \ge \mu$, both pointers are inside the cycle of length $\lambda$. Since $H$ closes the gap to $T$ by exactly $2 - 1 = 1$ edge per iteration, $H$ cannot jump over $T$ without landing on it. They meet at the smallest step $k \ge \mu$ where the distance between them $2k - k = k$ is an exact multiple of the cycle length $\lambda$: $$k = m \cdot \lambda \quad \text{for some integer } m \ge 1$$
• Phase 2 (Finding the Exact Cycle Entrance $\mu$): At the meeting step $k = m \lambda$, the Tortoise is at position $\mu + (k - \mu) \bmod \lambda$—meaning it has traveled $(k - \mu) \equiv -\mu \pmod \lambda$ steps past the cycle entrance $E$. Therefore, advancing a further $\mu$ steps along the cycle reaches offset $(k - \mu) + \mu = k = m \lambda \equiv 0 \pmod \lambda$, which is precisely the cycle entrance $E$! Resetting one pointer to head (distance $\mu$ from $E$) and advancing both pointers at speed 1 causes them to collide at $E$ after exactly $\mu$ steps.

Comparative Analysis of Cycle Detection Algorithms

Visualizing the $\rho$ (Rho) Cycle Geometry & Phase 2 Entrance Alignment

Functional Graph Reduction: Finding Duplicates in $O(1)$ Space Without Mutating Array

Production Implementation: Floyd's Entrance Finder & Brent's Cycle Detector

#include <cstddef>
#include <utility>
#include <vector>

struct ListNode {
  int val;
  ListNode* next;
};

// Floyd's Tortoise and Hare: Returns cycle entrance node (or nullptr if acyclic)
ListNode* floyd_find_cycle_entrance(ListNode* head) noexcept {
  ListNode* slow = head;
  ListNode* fast = head;

  // Phase 1: Find meeting point inside cycle
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) {
      // Phase 2: Reset one pointer to head; advance both at speed 1
      ListNode* finder = head;
      while (finder != slow) {
        finder = finder->next;
        slow = slow->next;
      }
      return finder; // Exact cycle entrance!
    }
  }
  return nullptr;
}

// Brent's Teleporting Turtle: Returns {cycle_entrance, cycle_length_lambda}
std::pair<ListNode*, std::size_t> brent_find_cycle(ListNode* head) noexcept {
  if (head == nullptr) return {nullptr, 0};

  std::size_t power = 1;
  std::size_t lambda = 1;
  ListNode* tortoise = head;
  ListNode* hare = head->next;

  // Phase 1: Find cycle length lambda with 1 pointer chase per iteration!
  while (hare != nullptr && tortoise != hare) {
    if (power == lambda) {
      tortoise = hare; // Teleport tortoise to hare
      power *= 2;
      lambda = 0;
    }
    hare = hare->next;
    ++lambda;
  }
  if (hare == nullptr) return {nullptr, 0};

  // Phase 2: Advance hare lambda steps ahead of head, then move both at speed 1
  tortoise = head;
  hare = head;
  for (std::size_t i = 0; i < lambda; ++i) {
    hare = hare->next;
  }
  while (tortoise != hare) {
    tortoise = tortoise->next;
    hare = hare->next;
  }
  return {tortoise, lambda};
}