jsschools

Floyd's Cycle Detection (Tortoise and Hare)

Detects cycles in a linked list (or any sequence defined by a next-state function) using two pointers moving at different speeds; also finds the cycle start and length.

Spec ↗

Syntax

floydCycle(head)

Parameters

NameTypeRequiredDescription
head ListNode | null Yes Head of a singly-linked list. Each node has a `val` and `next` pointer.

Returns

boolean — True if a cycle exists, false otherwise.

Examples

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

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

// Build: 1→2→3→4→2 (cycle at node 2)
const n1=new ListNode(1),n2=new ListNode(2),n3=new ListNode(3),n4=new ListNode(4);
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2; // cycle
console.log(hasCycle(n1));

const m1=new ListNode(1),m2=new ListNode(2);
m1.next=m2;
console.log(hasCycle(m1));
Output 
true
false

// Find the START of the cycle
class ListNode { constructor(val) { this.val = val; this.next = null; } }

function detectCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {
      // Reset one pointer to head; advance both one step at a time
      slow = head;
      while (slow !== fast) { slow = slow.next; fast = fast.next; }
      return slow; // cycle start node
    }
  }
  return null;
}

const a=new ListNode(3),b=new ListNode(2),c=new ListNode(0),d=new ListNode(-4);
a.next=b; b.next=c; c.next=d; d.next=b; // cycle starts at b
console.log(detectCycleStart(a)?.val);
Output 
2

Notes

| Case | Time | Space | |---------|------|-------| | Best | O(n) | O(1) | | Average | O(n) | O(1) | | Worst | O(n) | O(1) | **Why it works**: if a cycle of length λ exists starting at distance μ from the head, the slow and fast pointers will meet inside the cycle. After the meeting point, resetting one pointer to head and advancing both one step at a time will cause them to meet exactly at the cycle start (distance μ from the head). The algorithm applies to any function ƒ where the sequence x, ƒ(x), ƒ(ƒ(x)), … is eventually periodic — useful for finding repeated states in pseudorandom number generators.

See also