Floyd’s cycle detection

I spent two hours trying to understand the Floyd’s cycle detection algorithm (also known as the Tortoise and Hare algorithm) for several problems in LeetCode. Later, I realized that the guides weren’t confusing, they were incomplete about the crucial details.

The algorithm never clicked for me. Like, the Slow pointer moved a single step, while the fast pointer moved two steps- But what exactly did ‘steps’ mean?

It turns out there are two critical things every guide assumes you understand but never explicitly states.

1. What ‘steps’ actually mean in the context of this algorithm ?
2. How exactly is the solution guaranteed to be correct ?

First lets delve into the inner workings of the algorithm and discover the details about the ‘steps’ and constraints along the way.

Inner workings of the algorithm

Floyd’s cycle detection is a two step process.

1. Find the intersection point that creates the cycle.
2. Find the starting point of the said cycle.

Phase 1: Finding the intersection point.

To find the intersection point. Floyd’s cycle detection algorithm uses two pointers named slow and fast (or Hare and Tortoise) respectively. The slow pointer in this case moves one ‘step’ at a time, While fast pointer moves two ‘steps’ at a time.

The understanding of what ‘steps’ mean in the context will be crucial for working with the algorithm. To make it easier, below is a diagram representing how both pointers move across a linked list.

Lets consider a singly linked list with the Nodes A,B,C and D. Where there is a cycle formed within B, C and D.

We can now start “finding the intersection” phase of Floyd’s cycle detection problem. Each iteration and movement of fast and slow pointers are as depicted below.

We now have found the intersection point where fast and slow pointers meets. Our first phase of cycle detection is over.

The code equivalent for the above steps in phase 1 is as below.

1
// Both slow and fast starts from the same point
2
slow = head
3
fast = head
4

5
while(fast && fast -> next){
6
    // Moves one step or node in each iteration
7
    slow = slow -> next;
8

9
    // Moves two steps or nodes at each iteration
10
    fast = fast -> next -> next;
11

12
    // stops on finding intersection
13
    if (slow == fast){
14
        break;
15
    }
16
}

Phase 2: Finding the cycle entrance

To find the cycle entrance we only need to do a few changes to the previous process.

1. Reset the slow pointer to the initial node (i.e Node A).
2. Move both pointers only one step on each iteration.

Continuing from where we left off in the phase 1, once we apply the above changes we will have Slow pointer at Node A and Fast pointer at Node D.

Moving exactly one step from both pointers each iteration gives us the below depicted result where both nodes again meet at B just in a single iteration.

The code equivalent for the above steps in phase 2 is as below.

1
// Reset slow to the initial point.
2
slow = head;
3

4
// Move both single step until they meet again
5
while (slow != fast) {
6
    slow = slow->next;
7
    fast = fast->next;
8
}
9

10
// They meet at the entrance of the cycle!
11
return slow;

Now that we know how Floyds cycle detection works. We can proceed to understanding why it works.

We will try to answer the following questions in detail.

1. Why two different pointers ?
2. Why does phase 2 work completely different from phase 1?
3. How do they meet exactly at the cycle entrance in phase 2?

Understanding why Floyds cycle detection works

Why two pointers in different speeds ?

To understand this requirement better. Let us consider a Tortoise traversing a track that contains a circular loop within.

For the sake of clarity lets assume there is no marker in the track for the Tortoise to identify its position. With these two constraints we can conclude that the Tortoise will never be able to tell if it’s stuck in a loop without having any point of reference.

The same applies to a single pointer traversing through a linked list with a cycle. The pointer cannot identify if its stuck in a loop without having any reference.

Now add a Hare to the mix. Just like our fast pointer, Hare runs twice as fast as Tortoise. In our case the track contains a loop, Tortoise and Hare start at the same point. Lets assume that both of them managed to get stuck in a loop.

In case of a loop we know that the fastest one will always lap the other in a circular track, and to lap the Tortoise, Hare must meet it more than once since the start. This meeting is our derived intersection point.

This is why its guaranteed that the both pointers will meet at some point if a cycle exists.

Why does phase 2 work completely different from phase 1?

In phase 1 the goal was to identify one of the intersections of the existing cycle. In phase 2 the goal is to identify the starting point that leads both of them to the said intersection.

Because we have two different goals. It is necessary to take two different approaches.

How do they meet exactly at the cycle entrance in phase 2?

You might have noticed that resetting the slow pointer to initial node and Continuing the fast pointer from where it left off initially doesn’t make sense at all.

Here is exactly where we need to change our thinking a little. Instead of thinking them as fast and slow pointers we can now think of them as two different pointers starting from either side of the existing loop. This is because we know the following facts clearly.

1. The node pointed by our fast pointer is the first point of intersection since the start.
2. Since the fast pointer travelled twice as fast as slow pointer. It must also have covered twice the distance covered by slow pointer.

Resetting the slow pointer now while keeping the fast pointer exactly as it is ensures that both of them are at exactly equal distance from the cycle entrance. Now traversing in same speed from both direction results in them meeting at the entrance of the discovered loop.

But wait, why is resetting one of the pointers always lead them to the entrance? This is where the solution get interesting.

In phase 1,

The distance travelled by Tortoise can be summed up as,

Distance to the entrance of the loop + some amount of distance by Tortoise into the loop

The distance travelled by Hare can be summed up as,

Distance travelled by Tortoise + (n * length of the loop)

This is because the hare is guaranteed to lap the Tortoise more than once to meet the second time in a loop.

Now lets move to phase 2,

1. Tortoise moves from beginning traversing same distance as the Hare in each iteration.
2. Hare continues from where it left off. In this case it completes the remaining distance to the loop at same speed as Tortoise.

But this time both end up meeting at the same place covering same amount of distance due to traversing in equal speed.

Now we know two things for certain.

1. This point of meeting exists within the loop because we know the Hare cannot move out of the loop.
2. The Tortoise cannot travel past the entrance as the distance math guarantees that the hare will meet it at the entrance.

And this is the magic of Floyd’s algorithm. The double speed relationship between pointers creates a perfect distance symmetry.

Conclusion

Floyd’s cycle detection is elegantly simple once you understand the following.

1. One and Two steps means following the pointers through once and twice respectively.
2. The 2x speed creates the mathematical guarantee for finding the cycles.
3. The same distance and speed and relationship in phase 2 ensures that both pointers meet exactly at the entrance.

At its core the algorithm is just two pointers racing at different speeds until they meet (ensuring presence of a loop) and then walking together from either sides to find where the loop begins.