Floyd's Cycle-Finding Algorithm for Linked Lists

1. The Brute-Force Approach: Hashing Visited Nodes

The most direct way to think about this problem is to consider what defines a cycle. A cycle exists if, during our traversal of the list, we encounter a node that we have already visited. The first time we encounter such a "repeat" node, we have found the starting point of the loop.

How can we keep track of visited nodes? A hash set is a perfect data structure for this. We can traverse the list one node at a time, and for each node:

1. Check if the node is already in our hash set.
2. If it is, we have found the start of the cycle. We can immediately return this node.
3. If it isn't, we add the node to the hash set and move to the next node.

If we traverse the entire list and reach null without finding a repeated node, we can conclude that no cycle exists.

The following video from the takeUforward channel provides an excellent walkthrough of this hashing-based strategy.

To reinforce this, you can also read through the following text resource, which lays out the algorithm and provides a clean Java implementation.

This method is correct and easy to understand.

• Time Complexity: O(N), as we visit each node at most once. Hash set lookups and insertions take, on average, O(1) time.
• Space Complexity: O(N), because in the worst-case scenario (a list with no cycle), we would store every single node in the hash set.

For interviews at top companies, you'll be expected to do better. The O(N) space complexity is the key issue an interviewer would want you to optimize. This brings us to the optimal approach.

2. The Optimal Approach: Floyd's Cycle-Finding Algorithm

Here is where the slow-fast pointer technique we learned previously truly shines. It allows us to solve this problem in O(1) space. The algorithm is a two-step process:

1. Detect the Cycle: Use slow and fast pointers to determine if a cycle exists.
2. Find the Starting Node: If a cycle is detected, use the pointers' meeting point to find the cycle's entry point.

Step 1: Detecting the Cycle

We start both a slow and a fast pointer at the head of the list.

• slow moves one node at a time (slow = slow.next).
• fast moves two nodes at a time (fast = fast.next.next).

If the linked list has no cycle, the fast pointer will eventually reach the end of the list (null). However, if there is a cycle, the fast pointer will lap the slow pointer and they will eventually meet at some node within the cycle.

The intuition for why they must meet is based on their relative speed. Inside a cycle, the fast pointer gains on the slow pointer by one step for every move. Think of two runners on a circular track; the faster runner will inevitably lap the slower one.

The video below explains this detection phase and provides the crucial proof for why collision is guaranteed.

The condition for the traversal loop is while (fast != null && fast.next != null). If this loop finishes, it means no cycle was found. If slow == fast at any point inside the loop, we have detected a cycle and can proceed to the next step.

Step 2: Finding the Cycle's Starting Point

Once slow and fast have met at a collision point, we can find the start of the loop with a clever reset. The algorithm is as follows:

1. Leave the fast pointer at the collision point.
2. Reset the slow pointer back to the head of the linked list.
3. Now, move both slow and fast one step at a time (slow = slow.next, fast = fast.next).
4. The node where they meet again is the starting point of the loop.

This works due to a neat mathematical property. It can be proven that the distance from the head of the list to the start of the loop is equal to the distance from the collision point to the start of the loop.

The proof for this is fascinating and relies on the distances covered by each pointer. The following video and text resource walk through this logic beautifully.

For a written explanation and the final Java code, please review the optimal approach in the takeUforward article.

This optimal algorithm achieves the best possible complexities:

• Time Complexity: O(N), as the pointers traverse the list a constant number of times.
• Space Complexity: O(1), as we only use two extra pointers (slow and fast).

Practice Problems

Now you are equipped to solve two related LeetCode problems. The first asks you only to detect the cycle, and the second asks you to find its starting point.

1. LeetCode 141: Linked List Cycle (Detect if a cycle exists)
2. LeetCode 142: Linked List Cycle II (Find the node where the cycle begins)

Try to implement the solutions in Java using Floyd's algorithm from scratch.

Conclusion

In this lesson, we took the slow-fast pointer technique a step further, applying it to detect and locate cycles in a linked list. This pattern is a cornerstone of many advanced linked list problems and is frequently asked in technical interviews.

Key Takeaways:

• Brute-Force: A HashSet can track visited nodes to find a cycle's start in O(N) time and O(N) space.
• Floyd's Algorithm (Optimal): A two-step, O(1) space solution.
  • Step 1 (Detection): Move a slow pointer by one and a fast pointer by two. If they collide, a cycle exists.
  • Step 2 (Find Start): After collision, reset slow to the head. Move both slow and fast by one step until they meet again. This second meeting point is the start of the loop.
• The "Why": The mathematical proof, based on the distances traveled by the pointers, is what guarantees that this two-step process correctly identifies the starting node.

In our next lesson, we will shift our focus from manipulating a single list to operating on multiple lists by tackling another classic problem: merging two sorted linked lists.