algorithm - リンクリストでサイクルを識別するメソッドの背後にあるロジック

Question

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

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

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

Answer 1

フロイド法は、サイクルがあることを検出するのに役立ちますが、サイクルの開始前にいくつかのノードが存在する可能性があるため、サイクルの長さを直接指定することはできません。したがって、次のステップで長さを計算する必要があります。次に、サイクルの開始点を特定します。サイクルの長さはでKあり、ヘッドノードからサイクルの開始までのノード数はLです。両方のポインタを前方に移動すると、サイクルの開始時にそれらが合流します。これは、ヘッドポインタがLノードを前方に移動する必要があるKためです。先には2つの可能性があります。次の理由により、ノードの次のサイクルが確実に開始されLます。選択肢1：サイクル内にある場合は、サイクルのノード上にありK-LますK-(K-L) = L。選択肢2：サイクルから外れている場合、L-Kノードは最初とに残っていL-K + K = Lます。