Detecting and Locating Cycles in Linked Lists

Concept 1: Problem Definition and The Naive Approach

First, let's precisely define the problem. Given the head of a linked list, which may or may not contain a cycle, our task is to return the node where the cycle begins. If there is no cycle, we should return null.

Technical Explanation: The Hash Set Method

Before jumping to the optimal solution, let's consider a more straightforward approach. We can traverse the list one node at a time and store each node we visit in a hash set (or hash map). Before visiting a new node, we check if it's already in our set. The first time we encounter a node that's already in the set, we've found the starting point of the cycle.

This works correctly, but it comes at a cost. Storing every node requires extra memory. In the worst case, for a list of size $N$, the space complexity is $O(N)$. In an interview, you'd be immediately asked to optimize this.

Metaphor: Dropping Breadcrumbs

Imagine walking through a maze. The hash set method is like dropping a breadcrumb at every intersection you pass. If you arrive at an intersection and see a breadcrumb already on the ground, you know you've been there before and have just found a loop. It's effective but requires you to carry a large bag of breadcrumbs.

Python Code Snippet: Hash Set Approach

# Definition for singly-linked list node.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def findCycleStart_hashset(head: ListNode) -> ListNode:
    """
    Finds the start of a cycle using a hash set.
    Time Complexity: O(N)
    Space Complexity: O(N)
    """
    visited_nodes = set()
    current = head
    while current:
        if current in visited_nodes:
            # We've seen this node before, it's the start of the cycle.
            return current
        visited_nodes.add(current)
        current = current.next
    
    # If the loop finishes, there is no cycle.
    return None

This sets our baseline. Now, let's see how Floyd's algorithm achieves the same result with constant space.

Concept 2: Floyd's Algorithm - Phase 1: Collision

This first phase is exactly what we covered in the last lesson: detecting the cycle's existence. It's the "Tortoise and Hare" race.

Technical Explanation

We initialize two pointers, slow and fast, at the head of the list.

• slow moves one step at a time: slow = slow.next.
• fast moves two steps at a time: fast = fast.next.next.

If the list has no cycle, the fast pointer will eventually reach the end (None), and we're done. However, if a cycle exists, the fast pointer will enter it first and start "lapping" the slow pointer. Since the fast pointer gains one position on the slow pointer at every step within the cycle, they are guaranteed to meet. This meeting point is often called the "collision point".

Metaphor: Runners on a Track

Imagine two runners starting at the same time on a track that has a straight section leading into a circular loop. One runner is twice as fast as the other. They will both run the straight section, and then enter the loop. Once in the loop, the faster runner will inevitably lap the slower runner. The spot where they meet is the collision point.

To see this phase in action, let's watch a short video segment.

This collision proves a cycle exists, but the collision point is not necessarily the start of the cycle. That's what Phase 2 is for.

Concept 3: Floyd's Algorithm - Phase 2: Finding the Start Node

This is the clever part that builds on the collision from Phase 1.

Technical Explanation

Once slow and fast have collided, we do the following:

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 pointers one step at a time (slow = slow.next, fast = fast.next).

The node where they meet again is guaranteed to be the starting node of the cycle.

Metaphor: The "Magic" Reset

Think back to our runners. After the fast runner laps the slow one, they stop at the collision point. Now, we ask the slow runner to teleport back to the very beginning of the entire track (the head). We keep the fast runner at the collision spot. Then, we tell both runners to start jogging at the same, slow pace. The exact spot where they meet for the second time will be the entrance to the circular loop.

The video we just watched also covers this second phase beautifully.

Python Code Snippet: Full Floyd's Algorithm

def findCycleStart_floyd(head: ListNode) -> ListNode:
    """
    Finds the start of a cycle using Floyd's Tortoise and Hare algorithm.
    Time Complexity: O(N)
    Space Complexity: O(1)
    """
    if not head or not head.next:
        return None

    # Phase 1: Find the collision point.
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Collision detected. Break to start Phase 2.
            break
    else:
        # Loop finished without collision, no cycle.
        return None

    # Phase 2: Find the cycle start.
    # Reset one pointer to the head.
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    # Both pointers now meet at the cycle's start.
    return slow

Concept 4: The "Under the Hood" Mathematical Proof

Why does this "magic reset" work? It's not magic; it's math. This is the deep understanding that will impress an interviewer.

Technical Explanation

Let's use the variables from the diagram shown earlier:

• $L$: The distance from the head to the cycle's start node (length of the non-cyclic part).
• $a$: The distance from the cycle's start node to the collision point.
• $b$: The distance from the collision point back to the cycle's start node.
• $C$: The total length of the cycle, so $C=a+b$.

When slow and fast collide:

• Distance traveled by slow: $D_{slow}=L+a$
• Distance traveled by fast: $D_{fast}=L+a+n\cdot C$
  • The fast pointer has traveled the same path as slow, plus it has completed some number of full laps ($n\ge 1$) within the cycle.

We also know the fast pointer moves twice as fast as the slow pointer, so it has traveled twice the distance:
$D_{fast}=2\cdot D_{slow}$

Now, let's substitute the distance expressions:
$L+a+n\cdot C=2\cdot (L+a)$
$L+a+n\cdot C=2L+2a$

Rearranging the terms to solve for $L$:
$n\cdot C=L+a$
$L=n\cdot C-a$

This equation is the key. Let's make it more intuitive. We know $C=a+b$, so we can write $n\cdot C$ as $(n-1)\cdot C+C$:
$L=(n-1)\cdot C+C-a$
$L=(n-1)\cdot C+(a+b)-a$
$L=(n-1)\cdot C+b$

This equation tells us that the distance from the head to the cycle start ($L$) is equal to some number of full laps plus the distance from the collision point to the cycle start ($b$).

This is precisely why Phase 2 works! When we put one pointer at the head (which will travel a distance of $L$) and another at the collision point (which will travel a distance of $b$ to get to the start), they are guaranteed to meet at the cycle's start node.

For a rigorous walkthrough of this derivation, the following video is one of the best available.

Concept 5: Complexity, Trade-offs, and Real-World Relevance

Understanding the algorithm is one thing; articulating its performance and place in the world is another.

Technical Explanation: Performance Analysis

• Time Complexity of Floyd's: The slow pointer travels at most $N$ nodes before a collision. Phase 2 also takes a linear number of steps. The total time is therefore proportional to $N$.
• Space Complexity of Floyd's: The algorithm only requires two pointers, regardless of the list size. This is a constant amount of memory, making it $O(1)$.

Design Decisions & Interview Context
In an interview, you should first mention the hash set approach to show you can find a working solution. Then, immediately identify its space complexity as a drawback and introduce Floyd's algorithm as the optimized, $O(1)$ space solution. Being able to code it and then explain the mathematical proof for Phase 2 demonstrates a deep level of understanding that separates top candidates.

Real-World Applications
This isn't just an interview puzzle. The core idea of cycle detection appears in:

• Garbage Collection: Detecting circular references in memory to prevent memory leaks. If object A points to B, and B points back to A, neither can be automatically deallocated unless the cycle is detected.
• Finite State Machines: Determining if a state machine can get stuck in a loop.
• Cryptography: Pollard's rho algorithm for integer factorization uses a similar cycle-finding technique.

Conclusion

Today, you've fully dissected one of the most elegant algorithms in computer science. You not only learned the two-phase procedure of Floyd's Tortoise and Hare algorithm but also delved into the mathematical proof that underpins its correctness.

Key Takeaways:

• Two-Phase Approach: Floyd's algorithm solves this problem in two steps: 1) Detect a collision using fast and slow pointers. 2) Reset one pointer to the head, move both at the same speed, and their next meeting point is the cycle's start.
• Mathematical Foundation: The algorithm works because of a precise mathematical relationship: the distance from the head to the cycle start is equal to the distance from the collision point to the cycle start (plus some number of full cycle laps).
• Optimal Performance: The key advantage is its $O(1)$ space complexity, making it vastly superior to the $O(N)$ space hash set method. The time complexity remains linear, at $O(N)$.
• Interview Gold: This is a multi-layered problem perfect for interviews. Being able to explain the naive solution, the optimal algorithm, and the proof behind it showcases a robust problem-solving ability.

Preview of the Next Lesson

We have now concluded our deep dive into linear data structures and the clever pointer-based patterns used to manipulate them. We are moving into a new dimension of data organization: hierarchical structures. In the next lesson, you will learn to implement binary trees and perform the fundamental traversal algorithms (in-order, pre-order, post-order, and level-order). This will be our first step into the world of non-linear data structures, which are the foundation for search, indexing, and much more.