Cycle Detection | Floyd's Algorithm | Linked List

Overview

Cycle detection determines whether a linked list has a cycle: some node's next pointer points to an earlier node, so traversal would loop forever. Floyd's cycle-finding algorithm (tortoise and hare) uses two pointers moving at different speeds: if there is a cycle, they eventually meet; if not, the fast pointer reaches the end. It runs in O(n) time and O(1) space.

Why it works: In a cycle, the fast pointer gains one step per iteration relative to the slow pointer. So within at most one "lap" of the cycle after the slow enters it, fast catches up and they meet.

When to Use

Check if a list has a cycle — Has Cycle (return true/false).
Find the node where the cycle starts — Detect Cycle (return the node or null).
Find cycle length — After meeting, keep one pointer fixed and advance the other until they meet again; count steps.

How It Works

Phase 1 — Detect cycle:

Start slow = head, fast = head.
Each step: slow = slow.next, fast = fast.next.next (only if fast and fast.next are non-null).
If slow === fast, there is a cycle. If fast or fast.next is null, there is no cycle.

Phase 2 — Find cycle start (if cycle exists):

Set slow = head (or keep one at meeting point and move the other to head).
Move both one step at a time until they meet. The meeting node is the start of the cycle.

Intuition for phase 2: The distance from head to cycle start equals the distance from the meeting point to cycle start (when moving forward in the cycle). So advancing both from head and from the meeting point one step at a time makes them meet at the cycle start.

Example 1: Has Cycle (Boolean)

Problem: Given the head of a linked list, return true if there is a cycle, else false.

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

Time: O(n), Space: O(1).

Example 2: Detect Cycle (Return Cycle Start Node)

Problem: If the list has a cycle, return the node where the cycle begins; otherwise return null.

function detectCycle(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast !== null && fast.next !== null) {
    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;
}

Time: O(n), Space: O(1).

Example 3: Cycle Length (Optional)

After phase 1, keep slow fixed and set curr = slow.next; advance curr until curr === slow and count steps. That count is the cycle length.

Edge Cases

Empty list — fast is null; return false / null.
Single node — fast.next is null; no cycle; return false / null.
Two nodes, no cycle — fast reaches null after one or two steps.
Two nodes, cycle — second points to first; slow and fast meet.
Cycle at head — last node points to head; phase 2 correctly returns head.

Common Mistakes

Not checking fast.next — Before fast = fast.next.next, ensure fast.next !== null.
Wrong phase 2 start — One pointer must go back to head; moving both from the meeting point only finds the meeting point again.
Using extra space — HashSet of visited nodes works but is O(n) space; Floyd is O(1).

Time and Space Complexity

Time: O(n) — each pointer moves O(n) steps.
Space: O(1) — two pointers only.

Summary

Floyd's algorithm: slow (1 step) and fast (2 steps); if they meet, there is a cycle. To find cycle start: reset one to head, move both 1 step until they meet.
Part of Fast and Slow Pointers; see that concept for the general pattern.

Cycle Detection (Floyd's Algorithm)