フロイドの循環探索アルゴリズムはリンクされたリスト内のループを効率的に検出しますか?

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

コンピューター サイエンスの基本的なデータ構造であるリンク リストは、要素のシーケンスを表すためによく使用されます。特定のシナリオでは、リンク リストにループが含まれる可能性があり、最後のノードが前のノードを指し、循環構造が作成されます。このようなループの存在を特定することは、リンク リストを含むさまざまな操作にとって重要なタスクです。

フロイドのサイクル発見アルゴリズム

ウサギとカメのアルゴリズムとしても知られるフロイドのサイクル発見アルゴリズムは、次の機能を提供します。リンクされたリスト内のループを検出する効率的な方法。このアルゴリズムは、リスト内で 2 つのポインター (参照) を異なる速度で移動する原理に基づいて動作します。

1. Tortoise (Slow Pointer): 一度に 1 ノードずつ前方に移動します。
2. Hare (高速ポインター): 一度に 2 ノードずつ前方に移動します。

原理:

• ループの存在: リストにループがある場合、カメとウサギは最終的に同じノードで出会い、ループの存在を示します。
• ループなし: リストにループが含まれていない場合、カメまたはウサギはリストの最後 (ヌル ポインター) に到達し、ループがないことを示します。

Java 実装

次の Java 関数は、Floyd のサイクル検索アルゴリズムを実装します。

<code class="java">boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer 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 must have a loop
            return true;
    }
}</code>

利点

Floyd のサイクル検索アルゴリズムには、次の利点があります。

• 一定の空間計算量: 必要なポインター (参照) は 2 つだけで、空間計算量は一定 (O(1)) になります。
• 線形時間計算量:アルゴリズムの時間計算量は O(n) です。ここで、n はリンク リスト内のノードの数です。

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