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

Detecting Loops in Linked Lists Using Floyd's Algorithm

Determining whether a given linked list contains a loop can be a challenging task in Java programming. A loop occurs when the final node in the list refers to a previous node instead of having a null reference.

To detect loops efficiently, developers often employ Floyd's cycle-finding algorithm, also known as the tortoise and hare algorithm. This algorithm uses two references, a slow and a fast one, which traverse the list at different speeds.

For example, the slow reference advances by one node while the fast reference advances by two nodes. If the linked list contains a loop, these references will eventually meet. On the other hand, if there is no loop, either the slow or fast reference (or their subsequent references) will become null before the other reaches the end of the list.

Here is a Java implementation of Floyd's algorithm:

<code class="java">boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}</code>

This algorithm takes O(1) space complexity and runs in O(n) time, making it both memory-efficient and reasonably time-consuming.

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