How Does Floyd\'s Cycle-Finding Algorithm Detect Loops in Linked Lists?

Efficient Loop Detection in Linked Lists

Detecting loops in linked lists is a classic interview question that requires a sophisticated understanding of data structures and algorithms. We present a meticulous solution to this problem using Floyd's cycle-finding algorithm.

Floyd's algorithm employs two references, one advancing one step at a time, and the other advancing two steps at a time. This differential speed ensures that if there is a loop in the list, the two references will eventually meet.

Here's a step-by-step breakdown of the algorithm:

1. Initialize two references, slow and fast, to the first node in the list.
2. Advance slow by one node and fast by two nodes at each step.
3. Check if either slow or fast becomes null. This indicates the absence of a loop.
4. Check if slow and fast are equal. If they are, a loop exists.

The following Java function implements Floyd's algorithm:

<code class="java">public static boolean hasLoop(Node first) {

    if (first == null) // List does not exist, no loop
        return false;

    Node slow, fast; // Create two references

    slow = fast = first; // Point both to the start of the list

    while (true) {

        slow = slow.next; // 1 hop

        if (fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false; // Next node null -> no loop

        if (slow == null || fast == null) // If either hits null, no loop
            return false;

        if (slow == fast) // If the two ever meet, we have a loop
            return true;
    }
}</code>

This algorithm has a constant space complexity, as it uses only two references, and a reasonable time complexity of O(n), where n is the number of nodes in the list.

The above is the detailed content of How Does Floyd\'s Cycle-Finding Algorithm Detect Loops in Linked Lists?. For more information, please follow other related articles on the PHP Chinese website!