Finding the Start of a Linked List Cycle

Welcome back! In our previous lesson, we established a powerful, constant-space method—Floyd's Tortoise and Hare algorithm—to determine if a linked list contains a cycle. We saw that if a fast pointer (moving two steps) and a slow pointer (moving one step) ever collide, a cycle is guaranteed.

Today, we address the natural follow-up question, a classic in technical interviews: how do you find the exact node where the cycle begins? We will see that the solution is a clever and elegant extension of the very same algorithm. By the end of this lesson, you will not only be able to implement the solution but also understand the mathematical reasoning that makes it work.

The Two-Phase Approach

Finding the cycle's start is a two-phase process that builds directly on what you already know.

Phase 1: Detect the Cycle
This is exactly what we covered in the last lesson. We use a fast and a slow pointer, starting from the head. We advance them at their respective speeds until they meet. If the fast pointer reaches null, there is no cycle. If they meet, we've found a collision point somewhere inside the cycle, and we proceed to Phase 2.

Phase 2: Pinpoint the Starting Node
Once the slow and fast pointers have collided, the magic happens. The algorithm is surprisingly simple:

1. Leave one pointer (say, the fast pointer) at the collision point.
2. Move the other pointer (the slow pointer) back to the head of the linked list.
3. Now, advance both pointers one step at a time.
4. The node where they meet for the second time is the starting node of the cycle.

This might seem like a non-obvious trick, but it is guaranteed to work. To understand why, we need to analyze the distances traveled by the pointers.

The "Why": Unpacking the Intuition

Let's break down the linked list into distinct parts to reason about the distances.

Let's define our terms based on this diagram:

• m: The distance from the list start (head) to the cycle start.
• n: The total length of the cycle.
• k: The distance from the cycle start to the meeting point.

When the slow and fast pointers collide at the meeting point in Phase 1:

• Distance traveled by slow pointer: m + k
• Distance traveled by fast pointer: It has traveled m + k and also completed some number of full laps (p) around the cycle. So, its distance is m + k + p * n.

Since the fast pointer moves twice as fast as the slow pointer, we have the crucial relationship:
Distance(fast) = 2 * Distance(slow)
$m+k+p\cdot n=2(m+k)$
$m+k+p\cdot n=2m+2k$
Now, let's isolate m:
$p\cdot n=m+k$
$m=p\cdot n-k$
This equation is the key. It might look a bit abstract, so let's rephrase it. We can rewrite p * n - k as (p - 1) * n + (n - k). This tells us:

The distance from the head to the cycle start (m) is equal to some number of full cycles plus the distance from the meeting point to the cycle start (n - k).

Because full cycles don't change the relative position within the loop, this means that if you start one pointer at the head (and travel m steps) and another at the meeting point (and travel m steps), they are guaranteed to meet at the cycle's starting node.

The following video provides an excellent, step-by-step visual and intuitive proof of this exact logic. Watching it will help solidify why this two-phase approach is correct.

Implementation

Now that you understand the logic, implementing it is straightforward. The code consists of two distinct loops: the first for Phase 1 (detection) and the second for Phase 2 (finding the start).

The structure of this code is a classic pattern for this problem. You first establish that a meeting point exists and then use that point as an anchor to find the cycle's entrance.

Complexity Analysis

• Time Complexity: $O(N)$. The first phase has the slow pointer traversing at most N nodes. In the second phase, the pointer starting from the head travels m steps to the cycle's entrance. Since m < N, the total time complexity remains linear.
• Space Complexity: $O(1)$. Just like in the previous lesson, we only use a few pointers, making this the optimal solution in terms of space.

Conclusion

In this lesson, we've extended our knowledge of Floyd's Cycle-Finding Algorithm to not just detect a cycle but to pinpoint its exact starting node. This demonstrates the depth and utility of the fast and slow pointer pattern.

Key Takeaways:

• Finding the cycle start is a two-phase algorithm.
• Phase 1 is cycle detection: find the collision point using fast and slow pointers.
• Phase 2 is finding the start: reset one pointer to the head, keep the other at the collision point, and move both one step at a time until they meet again.
• The mathematical insight underpinning this is that the distance from the head to the cycle start is equivalent (in terms of position within the cycle) to the distance from the meeting point to the cycle start.

We've now seen the fast and slow pointer pattern used to find the middle of a list and to solve cycle-related problems. In our next lesson, we will explore another creative application: determining if a linked list is a palindrome. This will require combining fast/slow pointers with another fundamental operation: list reversal.