Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

Floyd’s Cycle Detection Algorithm is a pointer algorithm that uses two pointers moving at different speeds to detect a cycle in a sequence of values, typically in a linked list. It is one of the most elegant solutions to the cycle detection problem and operates with O(n) time and O(1) space complexity.

This technique was developed by Robert W. Floyd and is widely known as the Tortoise and Hare algorithm, referencing Aesop’s fable.

Overview

Floyd’s Cycle Detection Algorithm is a powerful technique used to detect cycles in sequences where each element points to the next one. It applies to any structure where you can repeatedly move from one state to the next, including:

• Linked lists
• Iterative function sequences
• Jump arrays
• Functional graphs

Also known as the Tortoise and Hare algorithm, this method is simple yet efficient—running in O(n) time and O(1) space.

What Is a Cycle?

A cycle exists when, starting from an initial element and following transitions (or “next” steps), you revisit a previous element.

Not Valid Cycle

a->b->c->d->e->f
   ^     |     
   ------

How Floyd’s Algorithm Works

Floyd’s algorithm uses two pointers that traverse the sequence at different speeds:

• Tortoise (slow): advances one step at a time.
• Hare (fast): advances two steps at a time.

Algorithm Steps:

• Initialize slow and fast to the starting value x0.
• Repeatedly advance:
  • slow = f(slow)
  • fast = f(f(fast))
• If slow == fast, a cycle exists.
• If the function reaches a terminal state (e.g., None, or no next), then no cycle exists.

Why It Works

If a cycle exists, the faster pointer will eventually “lap” the slower one inside the cycle—similar to how a faster runner will eventually overtake a slower one on a circular track.

If there’s no cycle, the fast pointer will reach a terminal state and never meet the slow pointer.

Generalized Python Implementation

def floyd_cycle_detection(f, x0):
    
    # Phase 1: Detect if a cycle exists
    slow = f(x0)
    fast = f(f(x0))
    
    while slow != fast:
        
        if fast is None or f(fast) is None:
            return False  # No cycle
        
        slow = f(slow)
        fast = f(f(fast))

    return True  # Cycle detected

Finding the Start and length of the Cycle

If a cycle exists, you might want to find its starting point and length.

Step-by-step:

• Run Floyd’s algorithm to find the meeting point.
• Reset one pointer to the start, and move both at the same speed.
• The point where they meet is the start of the cycle.
• To find the cycle length, start from this node and count how many steps it takes to loop back.

General Python Code:

def floyd_find_cycle_start_and_length(f, x0):
    # Phase 1: Detect cycle and meeting point
    slow = f(x0)
    fast = f(f(x0))
    while slow != fast:
        if fast is None or f(fast) is None:
            return None, 0  # No cycle
        slow = f(slow)
        fast = f(f(fast))
    
    # Phase 2: Find cycle start
    slow = x0
    while slow != fast:
        slow = f(slow)
        fast = f(fast)

    # Phase 3: Find cycle length
    start = slow
    length = 1
    fast = f(slow)
    while fast != start:
        fast = f(fast)
        length += 1

    return start, length

Practice

Conclusion

Floyd’s Cycle Detection algorithm is a beautiful example of a space-efficient solution using clever pointer manipulation. Understanding this algorithm also builds a foundation for solving more complex linked list and pointer problems.