Detecting Cycles in Linked Lists: Floyd's Tortoise and Hare

1. The Problem: A Loop in the List

A standard, or "linear," singly linked list terminates when a node's next pointer is NULL. However, due to a bug or by design, a node's next pointer could point to a preceding node in the list. This creates a cycle, or loop.

The primary danger of a cycle is that any code attempting a standard traversal (e.g., while (node != NULL)) will fall into an infinite loop, potentially crashing the program or causing it to hang. Your task is to write a function that, given the head of a list, can efficiently determine if such a cycle exists.

2. A First Idea: Hashing Visited Nodes

Before we get to the optimal solution, let's consider a straightforward approach. As we traverse the list, what if we just kept a record of every node we've already visited?

The natural way to do this is with a hash set (or hash map), where we store the memory address of each node we encounter.

The algorithm would be:

1. Initialize an empty hash set.
2. Start traversing the list from the head.
3. For each node, check if its memory address is already in the hash set.
   • If yes, we've visited this node before. A cycle exists. Return true.
   • If no, add the node's address to the hash set and move to the next node.
4. If the traversal reaches NULL, the list is linear. Return false.

Let's watch a brief explanation of this method.

This approach works, but as the video points out, it has a significant drawback:

• Time Complexity: O(n), as we visit each node once.
• Space Complexity: O(n), because in the worst case (a linear list), we store a pointer to every single node in the hash set.

For many applications, and especially in the memory-constrained environments of automotive and embedded systems you're familiar with, an O(n) space requirement is unacceptable. This is what motivates the search for a more optimal, O(1) space solution.

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

The optimal solution is a clever two-pointer algorithm named after its inventor, Robert W. Floyd. It's often called the "Tortoise and Hare" algorithm.

The idea is simple:

1. Initialize two pointers, slow (the tortoise) and fast (the hare), both pointing to the head of the list.
2. In a loop, advance the pointers at different speeds:
   • slow moves one step at a time: slow = slow->next;
   • fast moves two steps at a time: fast = fast->next->next;
3. Evaluate their positions:
   • If the list is linear, the fast pointer will reach the end (NULL) first. If this happens, we know there is no cycle.
   • If a cycle exists, the fast pointer will enter the cycle first, followed by the slow pointer. They will then chase each other around the cycle, and because fast is gaining on slow, they are guaranteed to eventually meet at the same node.

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

This video provides an excellent visualization of the algorithm in action and the intuition behind why it works.

The core takeaway from the proof is that because the fast pointer moves two steps for every one step of the slow pointer, the distance between them (within the cycle) decreases by one at each iteration. No matter how large the initial distance is, it will inevitably shrink to zero, guaranteeing a collision.

4. C Implementation and Analysis

Now, let's translate this elegant algorithm into C code. Given your background, the implementation should feel straightforward.

The core of the implementation is the while loop:

int detectLoop(struct Node* head) {
    struct Node *slow = head, *fast = head;

    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return 1; // Cycle detected
        }
    }
    return 0; // No cycle
}

The loop condition while (slow && fast && fast->next) is critical for safety. It ensures we never try to dereference a NULL pointer.

• slow: Checks if the slow pointer is valid.
• fast: Checks if the fast pointer is valid.
• fast->next: This is the most important check. It ensures that if fast is at the last node of a linear list, we don't try to access fast->next->next, which would be a NULL pointer dereference.

Complexity Analysis

• Time Complexity: O(n). The slow pointer traverses at most n nodes. The fast pointer traverses at most 2n nodes. The complexity is linear with respect to the number of nodes in the list.
• Space Complexity: O(1). We only use two extra pointers (slow and fast). The memory usage is constant and does not depend on the size of the list. This is a massive improvement over the hashing method.

5. Bonus: Finding the Start of the Cycle

In an interview, a common follow-up question is: "Now that you've detected a cycle, can you find the node where the cycle begins?" Floyd's algorithm can be extended to do this with a second phase.

Algorithm to Find Cycle Start:

1. Run the Tortoise and Hare algorithm until slow and fast meet. Let's call this the meetingPoint.
2. Do not move the fast pointer from the meetingPoint.
3. Reset the slow pointer back to the head of the list.
4. Now, advance both slow and fast one step at a time (slow = slow->next;, fast = fast->next;).
5. The node where they meet again is the starting node of the cycle.

This works because of a neat mathematical property: the distance from the head to the cycle start is equal to the distance from the meetingPoint to the cycle start (modulo the cycle length).

The following video provides a fantastic mathematical proof and code implementation for this second phase.

Conclusion

You have now analyzed and implemented Floyd's Tortoise and Hare algorithm, a cornerstone of pointer-based problem-solving. It's a testament to how a deep understanding of pointer mechanics can lead to exceptionally efficient and elegant code.

Key Takeaways:

• A cycle in a linked list can cause infinite loops and must be detected.
• A hash set provides a simple but space-inefficient O(n) solution.
• Floyd's Tortoise and Hare algorithm uses a slow and fast pointer to detect a cycle in O(n) time and O(1) space.
• The while (slow && fast && fast->next) condition is crucial for avoiding NULL pointer dereferences.
• If a cycle exists, the pointers are guaranteed to meet.
• The algorithm can be extended to find the starting node of the cycle by resetting one pointer to the head after the initial meeting.

Preview of the Next Lesson

Having seen the power of the two-pointer technique in the context of linked lists, we will next explore how this same powerful idea can be applied to a different data structure. In our next lesson, we will implement in-place array manipulation algorithms (e.g., reversing, partitioning) using the two-pointer technique. This will further solidify your ability to solve a wide range of common interview problems efficiently.