Chapter 02 - Topic 2.5

Floyd Cycle Detection

Floyd's algorithm uses two pointers moving at different speeds. If the list contains a cycle, the fast pointer will eventually meet the slow pointer inside the loop.

floyd cycle detectionlinked list cycle detectionfast slow pointer cycletortoise hare algorithmdetect loop in linked list

Definition

Floyd cycle detection is a fast-slow pointer method used to determine whether a linked list contains a cycle without using extra memory.

Core Idea

The slow pointer moves one step at a time, while the fast pointer moves two steps.

If there is no cycle, the fast pointer reaches null first.

If there is a cycle, the speed difference guarantees a meeting point inside the loop.

Detailed Explanation

Floyd's cycle detection is elegant because it turns a structural question into a motion question. Instead of storing visited nodes, it relies on relative speed.

If the list contains a loop, the fast pointer keeps gaining on the slow pointer by one step each round inside the cycle. Eventually the gap becomes zero and they meet.

This pattern matters beyond cycle detection. It trains the exact same fast-slow intuition that is later used for middle-node and nth-from-end style problems.

Detect a cycle with fast and slow pointers

JavaScript

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) return true;
  }

  return false;
}

Explanation

If the structure is a normal list, fast eventually hits null. If a loop exists, the fast pointer keeps circling and eventually catches the slow pointer because it moves faster inside the same cycle.

Output

Returns true when a cycle exists, otherwise false

Real-life Example

Imagine two runners on a circular track, one running twice as fast. If both keep going, the faster runner must eventually catch the slower one.

When To Use It

Use it when you need to detect whether a linked list contains a loop.
Use it when memory should stay O(1) instead of using a visited set.
Use it as preparation for more advanced cycle-entry questions.

Common Mistakes

Forgetting to check both fast and fast.next before moving two steps.
Confusing intentional circular lists with accidental cycles in interview problems.
Thinking the pointers must start at different places for the algorithm to work.

Key Takeaways

Floyd's algorithm detects cycles without extra memory.
It is one of the cleanest examples of the fast-slow pointer pattern.
The same idea is often extended to find the start of the cycle too.

Practice Ideas

Detect whether a linked list has a cycle.
Find the entry point of the cycle after detection.
Compare Floyd's method with a HashSet-based method.

Frequently Asked Questions

Why does the fast pointer eventually meet the slow pointer?

Inside a cycle, the faster pointer gains one step on the slower pointer each round, so their distance eventually becomes zero.

Why not use a Set instead?

A Set works too, but Floyd's algorithm uses O(1) extra space and is the classic interview solution.

Floyd Cycle Detection

Definition

Core Idea

Detailed Explanation

Detect a cycle with fast and slow pointers

When To Use It

Common Mistakes

Key Takeaways

Practice Ideas

Frequently Asked Questions

Why does the fast pointer eventually meet the slow pointer?

Why not use a Set instead?

More DSA Topic Pages

Floyd Cycle Detection

Definition

Core Idea

Detailed Explanation

Detect a cycle with fast and slow pointers

When To Use It

Common Mistakes

Key Takeaways

Practice Ideas

Frequently Asked Questions

Why does the fast pointer eventually meet the slow pointer?

Why not use a Set instead?

More DSA Topic Pages