Intuition Behind Cycle-Finding Algorithm

Hello! In the last lesson, we saw how Floyd's "Tortoise and Hare" algorithm can detect a cycle in a linked list by finding a collision point. We also introduced the two-phase algorithm to find the cycle's starting node: after the collision, reset one pointer to the head, and advance both pointers one step at a time until they meet again.

Today, we'll dive deep into the elegant logic that guarantees this second phase works. This is a favorite topic in coding interviews because it tests not just whether you know the algorithm, but whether you truly understand why it's correct. Our goal is to build that core intuition, moving beyond simply memorizing the steps.

Setting the Stage: A Tale of Three Distances

To understand the logic, we must first precisely define the distances involved. Imagine a linked list with a cycle. We can break its structure into a few key segments.

Let's define our terms based on this structure:

• x: The length of the non-cyclic part of the list. This is the distance from the head to the start of the cycle.
• y: The distance from the start of the cycle to the meeting_point where the slow and fast pointers first collide.
• z: The remaining distance in the cycle, from the meeting_point back to the start of the cycle.
• L: The total length of the cycle. Therefore, L = y + z.

The Mathematical Insight

In Phase 1, the slow and fast pointers meet at the collision point. Let's analyze the total distance each has traveled.

• Distance traveled by the slow pointer: It travels the non-cyclic path and then part of the cycle to the meeting point. $${\text{dist}}_{\text{slow}}=x+y$$
• Distance traveled by the fast pointer: It travels the same path, but it also completes one or more full laps of the cycle before meeting the slow pointer. Let's say it completes k extra laps. $${\text{dist}}_{\text{fast}}=x+y+k\cdot L$$ (Here, k is a non-negative integer representing the number of full laps the fast pointer has completed relative to the slow pointer).

The fundamental relationship of the algorithm is that the fast pointer moves twice as fast as the slow pointer. So, when they meet, the fast pointer has traveled exactly twice the distance.

Now, we can substitute our distance expressions into this equation:

Let's simplify this to isolate x:

This equation is the key, but its meaning isn't immediately obvious. Let's rearrange it into a more intuitive form. Since the cycle length L = y + z, we can write L - y = z.

Let's rewrite k*L as (k-1)L + L:

Now, substitute L - y with z:

This final equation reveals the magic. It tells us:

The distance from the head to the cycle start (x) is equal to some number of full laps ((k-1)L) plus the distance from the meeting point back to the cycle start (z).

Because traversing a full lap (L) brings you back to the same spot within the cycle, this means that traveling x steps from the head will land you on the exact same node as traveling x steps from the meeting_point. And where is that node? It's the start of the cycle.

This is why Phase 2 works:

1. We place a pointer at the head (ready to travel x steps).
2. We place another pointer at the meeting_point (also ready to travel x steps).
3. When we advance them both one step at a time, they are guaranteed to collide after x steps, precisely at the cycle's entrance.

The following article provides an excellent, detailed explanation of this intuition, complete with a walkthrough and discussion of common pitfalls.

To see this logic explained visually, the following video offers a fantastic step-by-step proof. Hearing and seeing the derivation can often provide that final "click" of understanding.

Conclusion

You now possess the deep understanding behind one of the most elegant algorithms for linked lists. It's a beautiful example of how a simple observation about relative speeds can lead to a powerful, constant-space solution.

Key Takeaways:

• The algorithm to find a cycle's start is based on a precise mathematical relationship between the distances in the list.
• The core insight is derived from the fact that distance_fast = 2 * distance_slow.
• This leads to the crucial equation x = (k-1)L + z, which means the distance from the head to the cycle start (x) is effectively the same as the distance from the meeting point back to the cycle start (z), plus some full laps.
• This is why moving two pointers at the same speed—one from the head, one from the meeting point—causes them to collide at the cycle's entrance.

In our next lesson, we will continue exploring the fast and slow pointer pattern by combining it with another fundamental linked list operation—list reversal—to solve another classic problem: determining if a linked list is a palindrome.