フロイドのアルゴリズムはリンクされたリスト内のループをどのように検出するのでしょうか?

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

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

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

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

これは、フロイドのアルゴリズムの Java 実装です。 :

<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>

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

以上がフロイドのアルゴリズムはリンクされたリスト内のループをどのように検出するのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。