algorithm - 循環リンクリストを解決するアプローチは何ですか?

Question

循環リンク リストが与えられた場合、ループの先頭でノードを返すアルゴリズムを実装します。

定義: 循環リンク リスト: リンク リスト内でループを作成するために、ノードの次のポインタが前のノードを指す (破損した) リンク リスト。

例: 入力: A->B->C->D->E->C[前と同じ C] 出力: C

Answer 1

カメとウサギのアルゴリズムを使用できます。

1. 2 つのポインターから始めて、1 つtortoiseを 、もう1 つを と呼びます。hare
2. 各時間ステップで、カメを 1 回、ウサギを 2 回進めます。
3. 等しくなるまで繰り返す

これにより、ループ内の要素が得られます。ループの開始点を見つけるには:

1. カメを一歩ずつ進め、歩数を数えます
2. うさぎにたどり着くまで止まる

これにより、ループの長さを見つけることができます。次に、「リンクされたリスト」内の要素の数でsize-lengthある開始点を見つけるために時間をステップするだけです。size

これは、フロイドのサイクル検出アルゴリズムとしても知られています。

Answer 2

ループを検出するための一般的なアルゴリズムは、2 つのポインター/イテレーターがリストを進み、1 つずつ要素を進め、残りの 2 つを進めることです。2 つの反復子が同じ要素を指している場合、リストにループが発生します。

ループが見つかったら、セット内のすべての要素を収集し、そのセット内の要素が見つかるまでリストの先頭から開始します。この要素は、ループの「開始」と見なすことができます

Answer 3

最も単純なアルゴリズムは、データ構造を使用して、既にアクセスした要素を格納することです。ハッシュ テーブル (約 O(n)) または単純な並べ替えられた配列 O(nlog(n)) のいずれかを使用できます。

リンクされたリストがグラフであると仮定して、サイクル検出に一般的に使用されるアルゴリズムの 1 つを使用することもできます。