Course contentsShow
← Computer Science
Lesson 338 of 2,8728. Linked Data StructuresFree lesson

Detecting Cycles in a List

Floyd's cycle detection algorithm using slow and fast pointers to identify circular references.

Detecting Cycles in a List

You'll learn how to discover if a linked list loops back on itself using Floyd's cycle detection algorithm.

What's a Cycle?

Sometimes a linked list can form a loop: a node's next pointer points back to an earlier node instead of continuing forward or reaching NULL. This creates a circular path where traversing the list never ends—you keep visiting the same nodes over and over.

Floyd's Cycle Detection Algorithm

This clever technique uses two pointers moving at different speeds:

  • Slow pointer: moves one node at a time
  • Fast pointer: moves two nodes at a time

Both start at the head. If there's no cycle, the fast pointer reaches NULL first. But if there is a cycle, the fast pointer will eventually "lap" the slow pointer—they'll meet at the same node, like two runners on a circular track where one is twice as fast.

The Analogy

Imagine two people walking around a circular track. One walks normally, the other jogs at double speed. If the track loops back (a cycle exists), the jogger will eventually catch up to the walker. If the track has an end (no cycle), the jogger simply reaches the finish line first.

Why It Works

In a cycle, the fast pointer enters the loop first. Once both pointers are in the loop, the fast pointer closes the gap by one node per iteration. Eventually, the gap becomes zero—they meet. If no cycle exists, the fast pointer safely reaches NULL without ever meeting the slow pointer.

Key Takeaway: Floyd's cycle detection uses two pointers at different speeds—if they meet, a cycle exists; if the fast pointer reaches NULL, there's no cycle.