リンクリスト内のサイクルを検出

別のリンク リスト アルゴリズム。

リンクされたリスト内のサイクルを検出します。

これは実際にはそれほど悪いことではありません。 O(n) 回実行するには、少なくとも 3 つの異なる方法があります。

最も簡単な方法は、リンク リスト ノードを変更して、ノードが訪問されたかどうかを示すフラグを含める必要があります。リストを走査するときに、訪問済みのノードに遭遇すると、サイクルが発生します。

別の手法では、訪問したノードまたはそれらへの参照を含むハッシュマップを使用します。リストが走査されると、ノードまたはその参照がハッシュに挿入されます。ハッシュマップ内ですでに表現されているノードに遭遇した場合、サイクルが存在します。この手法では 1 回のトラバーサルのみが必要ですが、ハッシュマップのためにより多くのメモリが必要になります。

この投稿では、フロイドのアルゴリズムを使用してサイクルを検出します。とても簡単です。

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

この手法では、リストへの 2 つのポインターを使用します。リストが走査されると、1 つのポインターは一度に 1 つのノードを移動し、もう 1 つのポインターは一度に 2 つのノードを移動します。 2 つのポインターが出会うと、サイクルが存在します。

なぜこれが機能するのでしょうか?リストを走査するにつれて、2 つのポインター間の距離は増加します。サイクルがある場合、速いポインターは遅いポインターを「ラップ」します。

より効率的な実装はありますか?境界条件が欠落していませんか?コメント欄でお知らせください。

ありがとうございます!

この投稿とこのシリーズのすべての投稿のコードはここにあります

以上がリンクリスト内のサイクルを検出の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。