Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

/**
 * Floyd's Tortoise and Hare Cycle Detection — Two-pointer O(1)-space cycle entry (μ) & period (λ)
 * Time: O(μ + λ) | Auxiliary Space: O(1)
 */
export function floydCycleDetection(
  nextIndex: readonly number[],
  head = 0
): { hasCycle: boolean; cycleStart: number; cycleLength: number } {
  const step = (node: number): number => (node >= 0 && node < nextIndex.length ? nextIndex[node] : -1);
  let tortoise = step(head);
  let hare = step(step(head));

  while (tortoise !== -1 && hare !== -1 && tortoise !== hare) {
    tortoise = step(tortoise);
    hare = step(step(hare));
  }
  if (tortoise === -1 || hare === -1) {
    return { hasCycle: false, cycleStart: -1, cycleLength: 0 };
  }

  tortoise = head;
  while (tortoise !== hare) {
    tortoise = step(tortoise);
    hare = step(hare);
  }
  const cycleStart = tortoise;

  let cycleLength = 1;
  hare = step(cycleStart);
  while (hare !== cycleStart) {
    hare = step(hare);
    cycleLength++;
  }
  return { hasCycle: true, cycleStart, cycleLength };
}