Detecting Cycles with Fast and Slow Pointers

Welcome back! In our previous lesson, we explored the Two Pointers technique and saw a glimpse of the fast and slow pointer variation for finding the middle of a linked list. Today, we'll dedicate our entire session to this powerful sub-pattern, commonly known as Floyd's Cycle-Finding Algorithm or the Tortoise and Hare algorithm.

This is a classic and highly efficient pattern that frequently appears in technical interviews. By mastering it, you'll not only be able to detect if a linked list contains a cycle but also pinpoint the exact node where the cycle begins—all with optimal space complexity. This lesson will equip you to solve this entire class of problems with confidence.

1. The Challenge of a Cycle

A linked list is supposed to be a linear sequence of nodes, with the final node pointing to null. A cycle occurs when a node's next pointer refers back to a previous node in the list. This creates an infinite loop, which can cause any standard traversal algorithm to run forever.

Imagine a background job processing a list of tasks represented as a linked list. If a bug introduces a cycle, that job could get stuck, consuming CPU and memory indefinitely without making progress—a subtle but critical failure mode in a real-world system.

How can we detect such a cycle? The most intuitive approach is to keep track of every node we've visited.

As the video explains, using a hash set works perfectly but requires $O(N)$ extra space to store the visited nodes. For very large lists, this could be a significant memory overhead. This is precisely the kind of trade-off an interviewer will expect you to identify and optimize. Fortunately, there's a brilliant solution that uses only $O(1)$ space.

2. Phase 1: Detecting the Cycle with the Tortoise and Hare

This is where the Fast and Slow Pointers pattern shines. The idea is wonderfully simple:

1. Initialize two pointers, slow (the tortoise) and fast (the hare), both at the head of the linked list.
2. In each step of a loop, move slow by one node (slow = slow.next).
3. In the same step, move fast by two nodes (fast = fast.next.next).
4. If the list has no cycle, the fast pointer will inevitably reach the end (null), and we can stop.
5. If the list does have a cycle, the fast pointer will eventually lap the slow pointer, and they will meet at the same node.

The moment slow == fast, we have definitively detected a cycle.

The core intuition is like two runners on a circular track at different speeds. The faster runner will always lap the slower one.

For a more rigorous explanation of why they are guaranteed to meet, the NeetCode video provides an excellent mathematical walkthrough.

At this point, you can answer the LeetCode "Easy" version of this problem (141. Linked List Cycle), which only asks if a cycle exists. However, top-tier interviews often ask a follow-up: can you find the start of the cycle?

3. Phase 2: Finding the Cycle's Starting Node

This is where the true elegance of Floyd's algorithm comes into play. Simply finding the meeting point is not enough, as it's usually not the start of the cycle. The second phase of the algorithm finds the entry point with a clever maneuver:

1. Once slow and fast meet, leave the slow pointer at the meeting point.
2. Create a new pointer, let's call it p1, and place it back at the head of the list.
3. Now, advance both p1 and slow one step at a time (p1 = p1.next, slow = slow.next).
4. The node where they meet again is the starting node of the cycle.

This seems almost magical, but it's grounded in a solid mathematical proof. The resource from AlgoMonster provides one of the clearest explanations of this two-phase process and the underlying math.

To reinforce this mathematical proof with a more visual, step-by-step derivation, the following video is highly recommended.

4. Implementation and Practice

Now that you understand the theory behind both phases, let's look at how to put it into practice. Since you're proficient in Go and JavaScript, you can translate the logic into either language. The AlgoMonster resource provides a concrete example and discusses common implementation errors.

As a backend developer, you know that edge cases and null pointer exceptions are a common source of bugs. The condition while fast_pointer and fast_pointer.next: is critical for ensuring your fast pointer doesn't try to access next on a null object, which would crash the program.

Conclusion

Today we took a deep dive into Floyd's Tortoise and Hare algorithm, a cornerstone pattern for solving linked list problems. You are now equipped to handle a very common and multi-part interview question with an optimal, production-quality solution.

Key Takeaways:

• The Problem: Cycles in linked lists can cause infinite loops. A naive hash set solution works but uses $O(N)$ space.
• The Optimal Solution: Floyd's Cycle-Finding Algorithm provides an $O(N)$ time and $O(1)$ space solution.
• Phase 1 (Cycle Detection): Use a slow pointer (1 step) and a fast pointer (2 steps). A meeting (slow == fast) proves a cycle exists.
• Phase 2 (Finding the Start): After the meeting, reset one pointer to the head. Move both pointers one step at a time. Their next meeting point is the cycle's start.
• The "Why": The algorithm's correctness is based on a mathematical proof relating the distances from the head, the meeting point, and the cycle start.

In our next lesson, we will shift gears to a new algorithmic pattern called Merge Intervals. This pattern is essential for solving problems involving overlapping ranges, such as scheduling conflicts, geometric intersections, and data consolidation.