リンクリスト内の循環を検出するPythonプログラム

リンクリスト内のどのノードも NULL を指していない場合、リンクリスト内にサイクルがあると言われます。最後のノードはリンク リスト内の前のノードを指し、ループが作成されます。循環リンク リストには終点がありません。

以下の例では、最後のノード (ノード 5) は NULL を指していません。代わりに、ノード 3 を指し、ループを確立します。したがって、上記のリンクリストは無限にあります。

2 つのポインターを取得するためのアルゴリズムが速い場合と遅い場合がある

• 両方のポインターは、最初はリンクされたリストの HEAD を指します。

• 遅いポインタは常に 1 ずつ増加し、高速ポインタは常に 2 ずつ増加します。

• いつでも、高速ポインタと低速ポインタが同じノードを指している場合、リンク リストにはサイクルがあると言われます。

最後のノードが 2 番目のノードを指す、次のリンク リストの例を考えてみましょう -

スロー ポインターと高速ポインターは両方とも同じノードを指します。したがって、指定されたリンク リストには循環が含まれていると結論付けることができます。

リンクリストでサイクルが検出されました。

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