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

How to Identify Looping Structures in Linked Lists

In computer science, linked lists are ubiquitous data structures used to store and organize data. However, linked lists can exhibit a particular phenomenon known as a loop. A loop occurs when the final node in the list points to a node earlier in the sequence, creating an endless cycle.

To address this issue, programmers must deftly identify whether a linked list exhibits looping behavior. One reliable technique for loop detection is Floyd's cycle-finding algorithm, also known as the "tortoise and hare algorithm."

This algorithm operates on the principle of differential movement. By advancing one reference pointer (the hare) two nodes at a time while simultaneously moving another reference (the tortoise) one node forward, Floyd's algorithm effectively scans the linked list.

Depending on the structure of the linked list, two outcomes are possible:

• Looping List: If the linked list contains a loop, the tortoise and hare pointers will eventually intersect at the same node. This confirms the presence of a loop.
• Acyclic List: In the absence of a loop, either the tortoise or hare pointer will encounter a null value, indicating the end of the list without any looping behavior.

The following Java implementation of Floyd's algorithm can be used to determine if a given linked list contains a loop:

<code class="java">public boolean hasLoop(Node first) {
    if (first == null) {
        return false;
    }
    Node slow = first;
    Node fast = first;
    while (true) {
        slow = slow.next;
        if (fast.next != null) {
            fast = fast.next.next;
        } else {
            return false;
        }
        if (slow == null || fast == null) {
            return false;
        }
        if (slow == fast) {
            return true;
        }
    }
}</code>

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