17. Linked List Cycle Detection (Floyd's Algorithm)

Difficulty:EasyPattern:Fast & Slow PointersTime:O(n)Space:O(1)

Given head, the head of a linked list, determine if the linked list has a cycle in it.

How It Works & Algorithmic Design

Solves using Floyd's Tortoise and Hare Cycle Finding Algorithm:

Pointers: Initialize slow = head and fast = head.
Traversal: Advance slow by 1 step (slow = slow.next) and fast by 2 steps (fast = fast.next.next).
Meeting Point: If a cycle exists, the fast pointer will eventually catch up and equal the slow pointer (slow === fast $\to$ return true).
Termination: If fast === null or fast.next === null, a list tail was reached without a cycle $\to$ return false.

Why This Approach Works Best

Detects loops without requiring $O(n)$ extra memory hash sets, running in $O(n)$ time complexity and true $O(1)$ space.

Example Walkthrough

Input: 3 -> 2 -> 0 -> -4 (points back to 2)

Linked list with cycle.

Floyd's Trace: Slow steps by 1, Fast steps by 2 -> Fast overlaps Slow inside loop.

Pointers meet inside the loop.

Output: true

Cycle detected.

Answer: Floyd's Cycle Detection implementation

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;
}

💡 Use fast and slow pointers to detect cyclic references in linear time.

Key Takeaways

Fast pointer moves at double speed ($2x$).
If a cycle exists, fast pointer reduces distance by 1 node per iteration until meeting slow pointer.
Runs in $O(n)$ time using $O(1)$ auxiliary space.