Intuition for Floyd's Cycle Detection

This article explains my intuition behind Floyd’s Cycle Detection algorithm. You can find two related LeetCode problems here:

• Linked List Cycle
• Linked List Cycle II

Linked List Cycle is about detecting whether a cycle exists in a linked list. You’ll want to understand this first before moving on to Linked List Cycle II, which builds on it to implement Floyd’s full cycle detection algorithm.

Cycle Detection

Reference: Linked List Cycle I

To determine whether a linked list contains a cycle, we could use a hash map to record the addresses of all visited nodes. However, this approach is not memory-efficient for very long linked lists.

Instead, we can use a two-pointer approach: initialize two pointers, fast and slow, that traverse the linked list. The fast pointer moves twice as fast as the slow pointer. If a cycle exists, fast will eventually catch up to slow. If no cycle exists, fast will reach the end of the list.

Why does this work? Let’s prove this by contradiction. Assume there is a cycle in the linked list, but fast and slow never meet. We know that within the cycle, fast will eventually lap slow. Consider the moment just before fast overtakes slow for the first time:

• Situation 1: fast is one node behind slow. After the next step (where fast moves two nodes and slow moves one node), they meet at slow.next.
• Situation 2: fast and slow are at the same node, meaning they’ve already met.

Therefore, we can use the condition fast == slow to detect a cycle.

Finding the Start of the Cycle

Case 1: Large Cycle, Short Linear Path

Let’s start by assuming the cycle is large and the linear portion of the linked list (before the cycle begins) is relatively short.

When fast and slow first meet at a point we’ll call meet, we can establish an relationship: the number of nodes from the start (head) to meet equals the number of nodes from meet back to meet when traversing the cycle.

Why? Since fast moves twice as fast as slow, when they meet, slow has traversed half the distance that fast has traversed (see the note at the end for a more precise explanation).

• Slow’s path: head → … → meet
• Fast’s path: head → … → meet, then meet → around the cycle → meet This means the path from head to meet equals the path from meet around the cycle back to meet.

Now, let’s introduce two new pointers, slow1 and slow2. Place slow1 at head and slow2 at meet. Move both pointers at the same speed:

• slow1 moves from head toward meet
• slow2 moves from meet around the cycle

Since they move at the same speed and traverse the same number of nodes, and they share a common path segment (from the cycle start to meet), they will meet at the cycle’s starting point.

Case 2: Small Cycle, Long Linear Path

Our previous analysis assumed a large cycle and short linear path. Now let’s consider the opposite: a small cycle with a long linear path. In this scenario, fast may complete several full cycles before meeting slow.

This slightly modifies our relationship: the distance from head to meet equals the distance from meet back to meet plus several complete cycles. However, this doesn’t change our technique for finding the cycle’s start point, because moving around complete cycles brings us back to the same position.

Important Note

The statement that “fast walks twice the path of slow when they meet” requires clarification.

While fast moves twice as fast as slow, the “double path” refers to edge path, not node count. For example, in the figure above:

• Fast visits: 13 nodes
• Slow visits: 7 nodes

But when measuring distances:

• Fast travels: 12 edge paths
• Slow travels: 6 edge paths

This is why we start slow2 at the meet point itself (not meet.next) — we want slow1 and slow2 to traverse the same number of nodes (not edge distances) when they eventually meet.

Implementation

The golang implementation is as follows:

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil 
    }
    slow, fast := head, head
    
    // Part 1: Detect if a cycle exists (Linked List Cycle I)
    for {
        if fast.Next == nil || fast.Next.Next == nil {
            return nil // No cycle
        }
            
        fast = fast.Next.Next
        slow = slow.Next
        
        if slow == fast { // Cycle detected
            break
        }  
    }
    
    // Part 2: Find the cycle's starting point
    // Reset slow to head
    // fast remains at the meet point
    // Here, slow is slow1 and fast is slow2 from our explanation
    slow = head 
    
    for {
        if slow == fast {
            break // Found the cycle start
        }
        
        slow = slow.Next
        fast = fast.Next
    }
    
    return slow   
}