別のリンク リスト アルゴリズム。
リンクされたリスト内のサイクルを検出します。
これは実際にはそれほど悪いことではありません。 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 サイトの他の関連記事を参照してください。