Detecting Cycles with Floyd's Algorithm

In our last lesson, we saw how the fast and slow pointer technique provides an elegant single-pass solution for finding the middle of a linked list. This pattern, where pointers move at different relative speeds, is a powerful tool for solving a variety of list-based problems.

Today, we will apply this same pattern to a different challenge: detecting a cycle. A linked list is supposed to be a linear structure, but if a node's next pointer refers to a previous node in the list, it creates a loop. Our goal for this lesson is to learn how to detect such a cycle efficiently using Floyd's Tortoise and Hare algorithm, a classic application of the fast and slow pointer method. This is a very common interview question, and understanding it deeply will solidify your grasp of pointer-based algorithms.

The Problem: What is a Cycle?

A cycle exists in a linked list if, by following the next pointers, you can eventually return to a node you have already visited. A standard, "healthy" linked list terminates with a null pointer. A list with a cycle does not; traversal will continue indefinitely within the loop.

For example, if a list is 1 -> 2 -> 3 -> 4, and node 4's next pointer points back to node 2, a cycle 2 -> 3 -> 4 -> 2... is formed. Our task is to write a function that returns true if a cycle exists and false otherwise.

A Baseline Solution: Using a Hash Set

Before diving into the optimal approach, let's consider a more straightforward solution. As you traverse the list, how can you remember which nodes you've already seen? A hash set (or hash map) is a natural fit for this.

The algorithm would be:

1. Initialize an empty hash set to store visited nodes.
2. Traverse the list one node at a time, starting from the head.
3. At each node, check if it's already in the hash set.
   • If it is, you've found a cycle. Return true.
   • If it's not, add the node to the hash set and move to the next node.
4. If you reach the end of the list (null), it means there was no cycle. Return false.

The following video explains this hashing-based approach clearly. Understanding this method provides a valuable point of comparison for the more efficient algorithm we'll learn next.

This approach works perfectly, but as the video notes, it has a significant drawback: its space complexity is $O(N)$, where $N$ is the number of nodes in the list. For a very large list, this can be a problem. The classic interview follow-up is, "Can you do it with $O(1)$ space?" The answer lies in Floyd's algorithm.

The Optimal Solution: Floyd's Tortoise and Hare Algorithm

We can adapt the fast and slow pointer technique from our previous lesson to solve this problem with constant space. The logic is as follows:

1. Initialize two pointers, slow (the tortoise) and fast (the hare), both at the head of the list.
2. In a loop, advance slow by one step and fast by two steps.
3. Consider the two possible outcomes:
   • No Cycle: If the list is linear, the fast pointer will simply run off the end, becoming null. If this happens, we know there is no cycle.
   • Cycle Exists: If there is a cycle, the fast pointer will enter it first, followed by the slow pointer. Once both are inside the cycle, they are like two runners on a circular track. Since the fast runner is moving faster, it is guaranteed to eventually lap the slow runner. In other words, they will collide—they will point to the same node.

If the pointers collide, we've detected a cycle. If the fast pointer reaches null, we know the list is linear.

The following image shows this process in action.

The key insight is that a collision is inevitable if a cycle exists. To understand why this is guaranteed, we need to think about the relative speed of the pointers.

This "gap closing" logic is the heart of the algorithm's correctness. Because the relative distance shrinks by a constant amount (one), it will eventually become zero.

Implementation and Complexity

Now that you have the intuition, the implementation is quite direct. It closely mirrors the code for finding the middle of a list, with the main difference being the logic inside the loop.

1. Initialize slow = head and fast = head.
2. Loop with the condition while (fast != null && fast.next != null). This check ensures the fast pointer can always make a two-step jump without causing a null pointer exception.
3. Move the pointers: slow = slow.next;, fast = fast.next.next;.
4. Check for Collision: After moving, check if slow == fast. If they are the same, a cycle is detected, and you can return true.
5. No Cycle: If the loop terminates (meaning fast or fast.next became null), it means no cycle was found. Return false after the loop.

The article below provides a clean implementation and a concise summary of the algorithm.

Complexity Analysis

The beauty of Floyd's algorithm lies in its efficiency.

• Time Complexity: $O(N)$. In the worst case (a linear list), the fast pointer traverses the entire list. If a cycle exists, the number of steps until collision is also proportional to the number of nodes in the list.
• Space Complexity: $O(1)$. We only use two extra pointers (slow and fast), regardless of the list's size. This is a major improvement over the hashing method.

Conclusion

In this lesson, we've explored a powerful application of the fast and slow pointer pattern to detect a cycle in a linked list. By moving two pointers at different speeds, we can identify a cycle in linear time and, most importantly, with constant extra space.

Key Takeaways:

• A cycle in a linked list can be detected by keeping track of visited nodes, for example with a hash set, which takes $O(N)$ time and $O(N)$ space.
• Floyd's Tortoise and Hare algorithm provides an optimal solution with $O(N)$ time and $O(1)$ space.
• The algorithm works by moving a slow pointer by one step and a fast pointer by two steps. A collision (slow == fast) proves a cycle exists.
• The core intuition is that once both pointers are in the cycle, the fast pointer closes the gap on the slow pointer by exactly one node at each iteration, guaranteeing an eventual collision.

You now know how to determine if a list has a cycle. But what if you wanted to know where that cycle begins? In our next lesson, we will build directly on today's algorithm to answer that very question, finding the starting node of the cycle.