単一リンクリストでサイクルを見つける
1. 概要
このチュートリアルでは、単一のリンクリストでサイクルを見つける問題と、このサイクルの開始点について説明します。
まず、問題の一般的な考え方を説明し、次にそれを解決するための2つのアプローチについて説明します。 次に、2つの例外的なケースを示し、それらを処理するためにアプローチの1つを更新する方法を確認します。
最後に、提供されているすべてのアプローチの比較を示します。
2. 問題の定義
ノードを持つリンクリストがあるとします。 リストが循環であるかどうかを確認したいと思います。 また、見つかった場合は、このサイクルの始まりを見つけたいと思います。
ソリューションを開始する前に、リスト内のサイクルが何を意味するかを知る必要があります。
ご存知のように、リストはノードのコレクションであり、各ノードには次のノードへの参照(つまり、リンク)が含まれています。 最後のノードがリスト内のノードの1つを指している場合、リストは循環的であると言います
理解を深めるために例を確認してみましょう。
リスト内に含めることができるサイクルは1つだけであることに注意してください。 さらに、各ノードが正確に1つのノードを指しているため、サイクルの原因は常に最後のノードがリスト内のノードを指していることです。
3. 訪問したアプローチ
3.1. 一般的なアイデア
サイクルのない単純なリストでは、次のようにループを使用してその要素を反復処理できます。
その理由は、サイクルがないため、最後の要素がを指しているためです。 非周期的リストを示す例を見てください。
ただし、サイクルがある場合、同じ方法で繰り返すことはできません。 その理由は、最後のノードが別のノードを指しているためです。 したがって、アルゴリズムは無限ループに入ります。
この問題を解決するために、各ノードに、以前にアクセスしたことがあるかどうかを示す変数を追加できます。 それを呼びましょう。
3.2. 実装
訪問したアプローチの実装を見てみましょう。
実装は2つの主要なステップで構成されています。
最初のステップでは、にサイクルがあるかどうかを確認します。 最初に、で初期化します。 これは、ループが見つからない場合、残りが残るようにするためです。
次に、イテレータを使用してノードを反復処理します。 各ステップで、以前に現在のノードにアクセスしたかどうかを確認します。 もしそうなら、それは私たちがサイクルに到達したことを意味し、現在のノードが開始点です。 したがって、内部に保存してループを停止します。
以前にこのノードにアクセスしたことがない場合は、アクセス済みとしてマークし、次の要素に進みます。
最初のステップが完了したら、リストを元の状態に復元するために、すべてのノードを未訪問としてマークします。 これは、この変数を他のアルゴリズムで使用できるようにするためです。
最後に、結果のを返します。
訪問されたアプローチの複雑さはです。ここで、はリストの長さです。
4. 訪問アプローチの特殊なケース
一部の問題やプログラム言語では、ノードの構造を編集するのが難しい場合があります。 その結果、変数を追加できない場合があります。 ただし、要素ごとに一意の変数がある場合があります。 それを呼びましょう。
4.1. 小さな整数ID
が範囲内の整数で、が比較的小さい場合は、要素を含む新しいブール配列を追加できます。 各ステップでは、要素内の値をチェックするのではなく、の値をチェックします。
実装を見てみましょう:
まず、で初期化します。これにより、結果の回答が保持されます。 また、配列をfalse値で初期化します。
次に、を繰り返します。 ノードごとに、以前にアクセスしたことがあるかどうかを確認します。 これを行うには、配列を使用します。
以前に訪れたことがない場合は、内部の場所に割り当てて、次の場所に移動します。 それ以外の場合は、ループを更新して中断します。
最後に、結果のを返します。
idの範囲がであるような負の値がある場合でも、すべての値を。だけシフトした後でも、このアプローチを使用できることに注意してください。 したがって、idの範囲はになり、idの位置はになります。
このアプローチの複雑さはです。ここで、はリストのサイズであり、はIDの最大値です。
4.2. TreeSetアプローチ
が整数でないか、値が比較的大きい場合、配列を使用することはできません。
実装を見てみましょう:
前のアプローチと同様に、で初期化します。これにより、結果の回答が保持されます。 さらに、訪問したIDを保持する新しい空のTreeSetとして定義します。
前と同じように、イテレータを使用して繰り返し処理します。 ただし、このアプローチでは、データ構造を使用して、訪問したノードに到達するかどうかを確認します。
の中に見つからない場合は、次の要素に移動してに追加します。 それ以外の場合は、を更新してループを解除します。
最後に、を返します。
このアプローチの複雑さはです。ここで、は要素の数です。
5. 2ポインターアプローチ
このセクションでは、リストからサイクルを見つけるための別のアイデアについて説明します。
5.1. 一般的なアイデア
まず、2つのイテレータを定義し、それらをで初期化します。
次に、を繰り返します。 毎回、1ステップ移動し、2ステップ移動します。 に到達するか、に等しくなるまで、このプロセスを続けます。
に達すると、サイクルが見つからないことを宣言します。 一方、に等しくなると、ループに到達し、そのノードの1つを指します。
サイクルの開始を見つけるには、最初にループのサイズを見つける必要があります。これは、ループが再び等しくなるまで移動し、ステップを数えることによってのみ実行できます。 したがって、で示されるサイクルのサイズを取得します。
5.2. 実装
実装を確認しましょう:
この実装は4つの部分に分割できます。
- サイクルがあるかどうかをチェックします。 これは、1ステップ、および毎回2ステップ移動することによって行われます。 プロセスは、彼らが出会うまで続きます。 彼らが出会ったとき、私たちはサイクルを見つけることを宣言します。 ループが終了したら、ループが見つかったかどうかを確認します。 その場合、アルゴリズムを返して終了します。
- のサイクルのサイズを計算します。 再び会うまで移動します。 最初は等しいので、ループの前に1回移動することに注意してください。
- に割り当てて、ノードを指すまで移動します。
- 彼らが出会うまで一緒に移動します。 彼らが会ったら、それらのいずれかを返します。
このアプローチの複雑さはです。ここで、はリストのサイズです。 線形の複雑さの背後にある理由を説明しましょう。
5.3. 2イテレータの概念実証
まず、2つのイテレータの背後にある考え方を説明しましょう。 はの2倍の速さで移動しているため、サイクルに入る最初の1つになります。 この後、サイクルに入ります。
この時点では、移動速度が速いため、ほとんどのステップで追いつくことができます。これが発生する前に、複数のケースがあります。
- 彼らが出会ったら、会いに戻ってきたので、私たちはサイクルを持っている必要があります。
- が1ステップ前の場合、次のステップでそれらが一致します。 したがって、サイクルがあります。
- が2ステップ前の場合、次のステップでは、が1ステップ前になります。これは、ケース2と同様です。
一般に、2ステップ前進するため、両方のイテレータ間の距離は、最終的に出会うまで毎回1ステップずつ減少します。
結果として、私たちがサイクルを持っている場合、それから追いつくでしょう、そして彼らはほんの数ステップ後に同じ場所で会うであろうと結論付けることができます。
5.4. サイクル開始ノードの概念実証
サイクルの開始を取得するために、ノードの最初とノードから開始しました。 彼らがたった1つのステップの後に会わなければならないことを証明しましょう。
まず、距離をに到達するために必要なステップ数として定義しましょう。 最初は、距離はに等しく、これはサイクルのサイズです。
両方のイテレータが同じ速度で移動するため、この距離は同じままです。 また、最初にサイクルに入り、その後にステップが続きます。 これが発生した場合でも、に到達するための手順が必要であると想定します。
ただし、どちらもサイクル内にあるため、前に進むと現在の位置に到達します。サイクルに要素があるためです。 したがって、ノードからステップを移動すると、同じノードに戻ります。
結果として、まだステップの前にある唯一の方法は、それらが同じノードにあるかどうかです。 したがって、このノードが開始ノードです。 また、サイクルの開始に到達するために多くのステップが必要です。
6. 比較
以前のアプローチの違いを見てみましょう。
メモリの複雑さは、リストによってすでに占有されているメモリに関係なく、追加で必要なメモリを意味します。
ご覧のとおり、訪問したアプローチは実装が簡単で、理解しやすいものです。 ただし、これを使用するには、リンクリストのノードに変数を追加する必要があります。 したがって、メモリの複雑さ。
一方、リスト内に小さな整数IDがある場合は、小さな整数のアプローチを使用することをお勧めします。
TreeSet アプローチに関しては、その複雑さは他のアプローチよりも大きくなります。 したがって、それは通常、一緒に行くのに最適なものではありません。
2ポインターアプローチは、あらゆるケースを処理できる一般的なアプローチです。 したがって、いつでも使用できます。
それでも、各要素を約6回繰り返すため、訪問したアプローチよりも少し時間がかかります。
7. 結論
このチュートリアルでは、単一リンクリストでサイクルを見つけることと、このサイクルの開始点について説明しました。
まず、問題の一般的な考え方を説明し、それを解決する2つのアプローチについて説明しました。 それ以外に、最初のケースに関連する2つの特別なケースを紹介しました。
最後に、時間とメモリの複雑さの観点から、すべてのアプローチを比較しました。 また、それぞれを使用するためのベストプラクティスについても説明しました。