c++ - フロイドのサイクル発見アルゴリズムが失敗するのはいつですか?

Question

フロイドの循環探索アルゴリズムに関するインタビューの質問を受ける:

フロイドのサイクル発見アルゴリズムが失敗するのはいつですか?

つまり、高速ポインターと低速ポインターの間のステップを見つけるためのルールはありますか?

Answer 1

合理的な仮定の下では、失敗することはありません。サイクルを見つけるか、サイクルがないと結論付けます。

私が考えることができる唯一の障害シナリオは、次の行に沿ったものです。

• 実装にバグがあります。
• トラバースされている構造は、アルゴリズムの進行中に変更されます。

Answer 2

Floyd のサイクル検出アルゴリズムに失敗する可能性はありません。

動的に変化するリンクされたリストで次のノードを見つけることが計算上困難な場合にのみ、起こりうる障害シナリオが発生します。