フロイドのアルゴリズムを使用したリンク リストのループの検出

指定されたリンク リストにループが含まれているかどうかを判断することは、Java プログラミングでは困難なタスクとなる場合があります。リストの最後のノードが null 参照ではなく前のノードを参照すると、ループが発生します。

ループを効率的に検出するために、開発者は多くの場合、カメとウサギのアルゴリズムとしても知られるフロイドのサイクル発見アルゴリズムを採用します。 。このアルゴリズムは、低速と高速の 2 つの参照を使用し、異なる速度でリストを走査します。

たとえば、低速参照は 1 ノード分進み、高速参照は 2 ノード分進みます。リンクされたリストにループが含まれている場合、これらの参照は最終的に一致します。一方、ループがない場合、低速参照または高速参照 (または後続の参照) のいずれかがリストの最後に到達する前に null になります。

これはフロイドのアルゴリズムの 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.
        }
    }
}

このアルゴリズムは、O(1) 空間の複雑さを必要とし、O(n) 時間で実行されるため、メモリ効率が高く、適度に時間がかかります。