Floyd's Cycle Detection: Tortoise and Hare

Key Insights

Floyd’s algorithm detects cycles in O(n) time with O(1) space by using two pointers moving at different speeds—the fast pointer will always catch the slow pointer inside a cycle
Finding the cycle’s starting node requires a second phase: reset one pointer to the head and move both at the same speed until they meet
This technique extends beyond linked lists to solve problems like finding duplicates in arrays without modifying the input or using extra space

Introduction to Cycle Detection

A cycle in a data structure occurs when a node references back to a previously visited node, creating an infinite loop. In linked lists, this happens when a node’s next pointer points to an earlier node. In graphs, cycles form when you can traverse edges and return to your starting vertex.

Detecting cycles matters more than you might think. An undetected cycle in a linked list causes infinite loops that hang your application. In garbage collectors, cyclic references can cause memory leaks. In state machines, cycles might indicate invalid transitions or deadlocks. In dependency resolution systems, cycles mean unresolvable dependencies.

The naive approach uses a hash set to track visited nodes. As you traverse, check if the current node exists in the set. If it does, you’ve found a cycle. This works, but requires O(n) space to store all visited nodes. When processing millions of nodes or running on memory-constrained systems, that overhead becomes unacceptable.

Floyd’s Cycle Detection algorithm solves this problem elegantly with constant space.

The Tortoise and Hare Algorithm Explained

The algorithm uses two pointers traversing the list at different speeds. The “tortoise” moves one step at a time. The “hare” moves two steps at a time. If there’s no cycle, the hare reaches the end and we’re done. If there’s a cycle, both pointers enter it and the hare eventually catches the tortoise.

Here’s the intuition: imagine two runners on a circular track. The faster runner will eventually lap the slower one. The same principle applies here. Once both pointers enter the cycle, the distance between them decreases by one with each iteration (the hare gains one position per step). They must eventually meet.

More formally: if the cycle has length C, and both pointers are in the cycle, the relative speed difference is 1 node per iteration. After at most C iterations, the hare catches the tortoise.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

The check fast and fast.next handles the termination condition. If either becomes None, we’ve reached the list’s end—no cycle exists.

Finding the Cycle Start Node

Knowing a cycle exists is useful, but often you need to know where it begins. Floyd’s algorithm has a second phase that finds exactly this.

After the tortoise and hare meet inside the cycle, reset one pointer to the head. Move both pointers one step at a time. They will meet again at the cycle’s entrance.

Why does this work? Let’s define some variables:

F = distance from head to cycle start
C = cycle length
a = distance from cycle start to meeting point

When they first meet, the slow pointer has traveled F + a steps. The fast pointer has traveled 2(F + a) steps. The fast pointer has also completed some number of full cycles, so:

2(F + a) = F + a + nC for some integer n

Simplifying: F + a = nC, which means F = nC - a

This tells us that the distance from head to cycle start (F) equals the distance from the meeting point to the cycle start going forward (C - a), plus some complete cycles. When we reset one pointer to head and move both at the same speed, they meet at the cycle start.

def find_cycle_start(head: ListNode) -> ListNode:
    if not head or not head.next:
        return None
    
    slow = head
    fast = head
    
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break
    else:
        # No cycle found
        return None
    
    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

Calculating Cycle Length

Once you’ve detected a cycle and found the meeting point, calculating the cycle’s length is straightforward. Keep one pointer fixed and move the other until they meet again, counting steps.

def find_cycle_length(head: ListNode) -> int:
    if not head or not head.next:
        return 0
    
    slow = head
    fast = head
    
    # Find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break
    else:
        return 0
    
    # Count cycle length
    length = 1
    current = slow.next
    while current != slow:
        length += 1
        current = current.next
    
    return length

Practical Applications

Linked List Cycle Detection (LeetCode 141/142)

The examples above directly solve LeetCode problems 141 (detect cycle) and 142 (find cycle start). These are classic interview questions that test your understanding of pointer manipulation and space optimization.

Finding Duplicates in Arrays

Here’s where Floyd’s algorithm really shines. Given an array of n+1 integers where each integer is between 1 and n inclusive, find the duplicate. The constraint: don’t modify the array and use only O(1) extra space.

The insight is treating the array as an implicit linked list. Each value points to the next index. A duplicate value means two indices point to the same “node,” creating a cycle. The duplicate number is the cycle’s entrance.

def find_duplicate(nums: list[int]) -> int:
    # Treat array as linked list: index -> nums[index]
    # nums[0] is the head
    
    slow = nums[0]
    fast = nums[0]
    
    # Phase 1: Find meeting point in cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Phase 2: Find cycle entrance (the duplicate)
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

This solves the problem in O(n) time and O(1) space, which is impossible with naive approaches.

Detecting Infinite Loops in State Machines

State machines can enter infinite loops when transitions create cycles without exit conditions. Apply Floyd’s algorithm by treating states as nodes and transitions as edges. If your “fast” state simulation catches up to the “slow” one, you’ve detected an infinite loop.

Complexity Analysis & Comparisons

Floyd’s algorithm runs in O(n) time. In the worst case, the slow pointer traverses the entire list once, and the fast pointer traverses it twice. Both phases together still give O(n).

Space complexity is O(1)—just two pointers regardless of input size.

The HashSet approach also runs in O(n) time but requires O(n) space. Here’s the comparison:

Approach	Time	Space	Pros	Cons
Floyd’s	O(n)	O(1)	Memory efficient	Slightly complex logic
HashSet	O(n)	O(n)	Simple to implement	Memory overhead

Use Floyd’s when memory is constrained or when processing large datasets. Use HashSet when code simplicity matters more and memory isn’t a concern.

Edge Cases and Implementation Pitfalls

Production code must handle edge cases gracefully. Here’s a robust implementation:

from typing import Optional, Tuple

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

def detect_cycle_complete(head: Optional[ListNode]) -> Tuple[bool, Optional[ListNode], int]:
    """
    Complete cycle detection returning:
    - has_cycle: whether a cycle exists
    - cycle_start: the node where cycle begins (None if no cycle)
    - cycle_length: length of the cycle (0 if no cycle)
    """
    # Edge case: empty list or single node without self-loop
    if head is None:
        return (False, None, 0)
    
    if head.next is None:
        return (False, None, 0)
    
    # Edge case: single node with self-loop
    if head.next == head:
        return (True, head, 1)
    
    slow: Optional[ListNode] = head
    fast: Optional[ListNode] = head
    
    # Phase 1: Detect cycle
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break
    else:
        # fast or fast.next is None - no cycle
        return (False, None, 0)
    
    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    cycle_start = slow
    
    # Phase 3: Calculate cycle length
    cycle_length = 1
    current = cycle_start.next
    while current != cycle_start:
        cycle_length += 1
        current = current.next
    
    return (True, cycle_start, cycle_length)

Key pitfalls to avoid:

Forgetting null checks: Always verify fast.next exists before accessing fast.next.next
Comparing values instead of references: Cycle detection requires comparing node identity, not values
Off-by-one errors in cycle length: Start counting from 1, not 0
Assuming head is in the cycle: The cycle might start several nodes into the list

Floyd’s Cycle Detection is one of those algorithms that seems like magic until you understand the math. Once you do, it becomes an indispensable tool for problems requiring constant space complexity. Master it, and you’ll have an elegant solution for a class of problems that would otherwise require auxiliary data structures.