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

リンク リスト内の効率的なループ検出

リンク リスト内のループの検出は、データ構造とアルゴリズムの高度な理解を必要とする面接の古典的な質問です。私たちは、フロイドのサイクル発見アルゴリズムを使用して、この問題に対する綿密な解決策を提案します。

フロイドのアルゴリズムは 2 つの参照を使用し、1 つは一度に 1 ステップずつ進み、もう 1 つは一度に 2 ステップずつ進みます。この差分速度により、リスト内にループがある場合、2 つの参照が最終的に一致することが保証されます。

アルゴリズムを段階的に説明します。

1. 2 つを初期化します。リストの最初のノードを低速と高速で参照します。
2. 各ステップで、低速と高速のいずれかが null になるかどうかを確認します。各ステップで 1 ノードずつ低速、2 ノードずつ高速に進みます。これはループがないことを示します。
3. 遅いと速いが等しいかどうかを確認します。存在する場合、ループが存在します。
4. 次の Java 関数は、フロイドのアルゴリズムを実装します。

このアルゴリズムは 2 つの参照のみを使用するため、一定の空間計算量を持ちます。妥当な時間計算量は O(n) です。ここで、n はリスト内のノードの数です。

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

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