問題タブ [floyd-cycle-finding]

亀とうさぎの会議はループの存在を結論付けていると理解していますが、待ち合わせ場所でうさぎを維持しながら、リンクリストの先頭に亀を移動し、その後、一度に両方を1ステップずつ移動すると、開始点で会うようになります。サイクルの？

.NET の C++ でこのアルゴリズムを見つけようとしていますが、できません。次のアルゴリズムを見つけました。

しかし、正しくないように思われますか、それとも間違っていますか? 最後にウサギがカメと出会うことを実際にどのように証明できますか? それがどのように正確に機能し、どのように機能するかについての説明を事前に感謝しますproof

編集済み

この解決策について、通常のアルゴリズムでは高速反復子を 1 つしか使用しないことがわかりましたが、ここでは 2 つを使用します。なぜですか?

リンクされたリストでループを見つけるアルゴリズムについて話している質問をすでに見ました。私はフロイドのサイクル発見アルゴリズムの解決策を読んだことがあります. 1 つのポインター (遅い/亀) が 1 増加し、他のポインター (速い/うさぎ) が 2 増加します。それらが等しい場合、ループが見つかり、より速いポインターが null に達すると、リンクされたリストにループはありません。

ここで私の質問は、なぜ高速ポインターを 2 ずつ増やすのかということです。結果を得るには、2 ずつ増やす必要があります。または、X だけ増やすこともできます。より速いポインターを 2 ずつインクリメントする場合にループを見つける必要がありますか、または 3 または 5 または x ずつインクリメントする必要がある場合があります。

関数 f があるとします。

f(0..12):

それぞれ 1 と 4 であるサイクルの開始とサイクルの長さを見つけたいと思います。カメとウサギのアルゴリズムは反復関数で機能しますが、反復関数はありません。反復されない関数で動作する他のアルゴリズムはありますか、またはこのために亀とウサギのアルゴリズムを変更できますか?

編集：

Jason S's answer を使用して、私はこれを思い付くことができました。これはうまくいっているようです:

リンクリストでサイクルを検出するために、2つのポインター（遅いポインターと速いポインター）を保持するHareandTortoiseアプローチを使用できることを理解しています。ただし、wikiやその他のリソースを読んだ後、2つのポインターがO（n）時間計算量で一致することが保証されている理由がわかりません。

リンクリスト内のサイクルを検出するための最良の方法では、次のようにします。

1. フロイドの循環検出アルゴリズムを使用して、リンクリスト内の循環内の位置を特定します。
2. リンクリストでサイクルのサイズを数えます
3. 1つのポインターをリストの先頭に配置し、別の「k」（kはサイクルのサイズ）を離して配置します。
4. 反復では、サイクルの開始時にそれらが出会います。

なぜこれが機能するのか知りたいのですが。この背後にあるいくつかの理論的論理？

インタビューの質問では、「ループの存在を検出するアルゴリズムを実装してください。」. たとえば、リンクされたリストには次のようなループがあります。

Floyd のサイクル検出を使用すると、高速 & 低速ポインターを使用することでこの問題を解決できます。じゃあ比較してみようかな

を。リンクのノード値、つまり

fast と slow はタイプですLink

また

b. それらは同じ参照を指していますか、つまりif (fast == slow)

ありがとう。

フロイドのサイクル発見アルゴリズムによると、カメとウサギが出会うポイントは、リンク リストの循環的な性質を説明しています。

サイクルの開始ノードを見つけるために、亀のポインターをリストの先頭に初期化し、ウサギと亀のポインターを 1 単位ずつインクリメントし始めます。それらが出会うポイントは、サイクルの開始ノードを示します。

特定の状況でどのように機能するか教えてください。

リンク リストは次のように流れます。

今日、リンクされたリストのループを検出するフロイドのアルゴリズムを読んでいました。ループ検出を高速化するために、複数のノード (たとえば 2 つ) をスキップした方がよいのではないかと思っていました。

例えば：

変更中は副作用が考慮されることに注意してくださいfastptr。