Floyd's Cycle-Finding Algorithm

1. A Straightforward but Inefficient Approach: Hashing

Before we dive into the optimal solution, let's consider a more intuitive approach. How can we detect a revisited node? By keeping a record of every node we've already seen.

The idea is simple:

1. Create a HashSet to store ListNode objects.
2. Traverse the linked list from the head.
3. For each node, check if it's already in the HashSet.
   • If it is, we've found a cycle! The current node is the starting point of the loop.
   • If it's not, add the current node to the HashSet and move to the next node.
4. If we reach the end of the list (null), it means no node was revisited, so there is no cycle.

This approach is correct, but what are its performance characteristics?

• Time Complexity: $O(N)$, where N is the number of nodes in the list, because we visit each node at most once.
• Space Complexity: $O(N)$, because in the worst case (a list with a cycle involving all nodes, or a linear list), we would store every node in the HashSet.

For an interview setting, an O(N) space complexity is often a signal to look for a more optimized, constant-space solution. Let's watch a short video segment that explains this hashing method.

2. The Optimal Solution: Floyd's Tortoise and Hare Algorithm

To achieve a constant space complexity, we can use a clever two-pointer technique. We'll use:

• A slow pointer that moves one step at a time (slow = slow.next).
• A fast pointer that moves two steps at a time (fast = fast.next.next).

The algorithm works in two distinct phases.

Phase 1: Cycle Detection

Both pointers start at the head. They then traverse the list at their respective speeds.

• If the list is linear (no cycle), the fast pointer will eventually reach the end (null), and we can conclude there's no cycle.
• If the list contains a cycle, the fast pointer will enter the loop and start circling. The slow pointer will eventually follow it into the loop. Since the fast pointer is moving faster, it will inevitably "lap" the slow pointer and they will collide at some node within the cycle.

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

This video segment recaps the detection phase.

Phase 2: Finding the Start of the Cycle

Detecting the cycle is only half the battle. The core of the problem is finding the exact node where the cycle begins. Here's the magic trick:

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

Let's see this second phase explained visually.

Why Does This Work? The Mathematical Intuition

You might be wondering why this procedure correctly identifies the start of the loop. It's based on the distances the pointers travel. Let's define:

• L1: The distance from the head to the start of the loop.
• L2: The distance from the start of the loop to the collision point.
• C: The length of the cycle.

When the slow and fast pointers collide:

• Distance traveled by slow pointer: D(slow) = L1 + L2
• Distance traveled by fast pointer: D(fast) = L1 + L2 + k * C (it has completed k extra laps of the cycle)

Since the fast pointer moves twice as fast, D(fast) = 2 * D(slow).
Substituting the distances:
L1 + L2 + k * C = 2 * (L1 + L2)
L1 + L2 + k * C = 2*L1 + 2*L2
k * C = L1 + L2
Rearranging this gives: L1 = k * C - L2

This equation is the key. It tells us that the distance from the head to the loop start (L1) is equal to some number of full cycles minus the distance from the loop start to the collision point (L2). This effectively means that the distance from the head to the loop start is the same as the distance from the collision point to the loop start, if you traverse forward inside the loop.

Therefore, by placing one pointer at the head and another at the collision point and moving them at the same speed, they are guaranteed to meet at the start of the loop.

The following video provides an excellent, detailed walkthrough of this proof. Understanding this is what separates a good candidate from a great one in an interview.

3. Java Implementation

Now, let's translate this two-phase algorithm into Java code. The structure directly follows the logic we've discussed.

Here's the implementation from the article, which perfectly captures the algorithm:

// Assuming a ListNode class is defined:
// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; next = null; }
// }

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null; // No cycle can exist
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Phase 1: Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Cycle detected, start Phase 2
                
                // Reset one pointer to the head
                slow = head;
                
                // Move both pointers one step at a time until they meet
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                
                // The meeting point is the start of the cycle
                return slow; 
            }
        }
        
        // If the loop finishes, fast reached null, so no cycle
        return null;
    }
}

• Time Complexity: $O(N)$. Although we have two loops, the pointers traverse the list a constant number of times in total, making it linear.
• Space Complexity: $O(1)$. This is the key advantage. We only use two pointers, regardless of the list's size.

Conclusion

Excellent work! You've just learned one of the most elegant algorithms for linked lists. It's a testament to how clever pointer manipulation can solve complex problems with remarkable efficiency.

Key Takeaways:

• Hashing vs. Floyd's: While hashing is an intuitive O(N) space solution, Floyd's Tortoise and Hare algorithm provides an optimal O(1) space solution.
• Two-Phase Process: Floyd's algorithm consists of two phases: first, detect a collision using slow and fast pointers, and second, find the cycle's start by resetting one pointer to the head and moving both at the same speed.
• The "Why": The algorithm works because of the mathematical relationship between the distance from the head to the loop start and the distance from the collision point to the loop start.

Preview of the next lesson:
The slow-and-fast pointer technique is incredibly versatile. In our next lesson, we will use it again to solve another common problem: finding the middle element of a linked list. This will help reinforce the pattern and show you how it can be adapted to different scenarios.