Cycle Detection in Linked Lists (Fast and Slow Pointers)

1. Understanding the Problem and a Brute-Force Solution

First, what does a cycle look like? Imagine a list where the last node's next pointer doesn't point to null, but instead points to the second node in the list. If you were to traverse this list, you would go from the head to the end, then jump back to the second node and repeat the loop forever.

A straightforward way to detect this is to keep track of every node you've visited. As you traverse the list, you can store each node in a HashSet. Before visiting the next node, you check if it's already in your set. If it is, you've found a cycle! If you reach the end of the list (null), then no cycle exists.

Let's watch a brief explanation of this hash map approach. It's a good starting point, but as you'll see, we can do better.

The main takeaway from this approach is its space complexity. Because we have to store every node we visit, the space required is O(n), where n is the number of nodes in the list. In an interview, you'll almost certainly be asked for a solution that uses constant space, O(1). This is where the Tortoise and the Hare algorithm comes in.

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

The core idea behind this algorithm is beautifully simple. We use two pointers, slow and fast, both starting at the head of the list.

• The slow pointer (the "tortoise") moves one step at a time (slow = slow.next).
• The fast pointer (the "hare") moves two steps at a time (fast = fast.next.next).

Think of two runners on a track. If the track is a straight line, the faster runner will simply finish first. But if the track is a loop, the faster runner will eventually lap the slower runner. The same logic applies here:

• If the linked list has no cycle, the fast pointer will reach the end of the list (null) first.
• If the linked list has a cycle, the fast pointer will eventually enter the loop and, at some point, meet the slow pointer from behind.

Why are they guaranteed to meet? Why won't the fast pointer just "jump over" the slow one? Let's explore the intuition.

Now that we have the intuition, let's look at a clear explanation and implementation in Java.

Here's how we could implement this hasCycle method within our SinglyLinkedList class:

public class SinglyLinkedList {
    // ... fields and other methods ...

    public boolean hasCycle() {
        if (head == null || head.next == null) {
            return false;
        }

        Node slow = head;
        Node fast = head;

        // The loop condition must check fast and fast.next to prevent NullPointerException
        while (fast != null && fast.next != null) {
            slow = slow.next;          // Move one step
            fast = fast.next.next;    // Move two steps

            if (slow == fast) {
                return true; // Collision detected, a cycle exists
            }
        }

        return false; // Fast pointer reached the end, no cycle
    }

    // ... Node inner class ...
}

This algorithm is highly efficient.

• Time Complexity: O(n). In the worst case, the pointers traverse the list once.
• Space Complexity: O(1). We only use two extra pointers, regardless of the list size. This is the optimal solution interviewers look for.

3. Follow-Up: Finding the Start of the Cycle

A common follow-up question is: "Great, you've detected a cycle. Now can you find the node where the cycle begins?"

This requires a second phase to our algorithm. The math behind this is quite elegant. Let's define some distances:

• m: The distance from the head to the start of the loop.
• k: The distance from the start of the loop to the meeting point of the slow and fast pointers.
• n: The total length of the cycle.

There's a fascinating mathematical property: the distance from the head to the start of the cycle (m) is equal to the distance from the meeting point back to the start of the cycle, plus some number of full laps.

The algorithm for finding the start node is:

1. Phase 1: Detect the cycle. Run the Tortoise and Hare algorithm until slow and fast meet. If they don't meet, there is no cycle.
2. Phase 2: Find the start node. Once they meet, reset one of the pointers (say, slow) back to the head. Keep the fast pointer at the meeting point.
3. Now, move both pointers one step at a time (slow = slow.next, fast = fast.next).
4. The node where they meet again is the start of the cycle.

Let's read a detailed explanation that includes the mathematical proof and a clear Java implementation.

Here's the combined method that returns the starting node of the cycle, or null if no cycle exists.

public Node detectCycle() {
    if (head == null || head.next == null) {
        return null;
    }

    Node slow = head;
    Node fast = head;
    boolean cycleExists = false;

    // Phase 1: Detect if a cycle exists
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            cycleExists = true;
            break;
        }
    }

    if (!cycleExists) {
        return null; // No cycle found
    }

    // Phase 2: Find the start of the cycle
    slow = head; // Reset slow pointer to the head
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow; // Both pointers now meet at the cycle's starting node
}

Conclusion

You've just added another powerful tool to your data structures and algorithms toolkit. The Tortoise and Hare algorithm is not just a trick; it's a prime example of how clever pointer manipulation can lead to highly efficient, space-optimized solutions.

Key Takeaways:

• A naive approach to cycle detection uses a HashSet, resulting in O(n) space complexity.
• The optimal solution is Floyd's Cycle-Finding Algorithm (Tortoise and Hare), which uses a slow and a fast pointer and achieves O(1) space complexity.
• If a cycle exists, the fast pointer (moving two steps) is guaranteed to eventually meet the slow pointer (moving one step).
• To find the start of the cycle, you use a two-phase approach: first detect the meeting point, then reset one pointer to the head and move both at the same speed until they meet again.

In our next lesson, we will shift gears from linked lists to another fundamental data structure: the stack. We'll implement a stack and use it to solve another classic interview problem, "Valid Parentheses."