単一リンクリストでサイクル開始ノードを検索します

1. 概要

このチュートリアルでは、リンクリストでサイクル開始ノードを見つける方法を学習します。また、各アプローチのさまざまな時間と空間の複雑さを分析します。さらに、最も効率的なアルゴリズムを見て、それを証明します。さらに、線形時間計算量を証明します。リンクリストのデータ構造とBig-O表記の基本的な知識があることを前提としています。

2. 問題文

単一リンクリストがあるとします。このリストにはサイクルがあります。したがって、私たちのタスクは、サイクル開始ノードを返すことです。与えられるのは、リンクリストヘッド（開始ノード）だけです。理解を深めるために例を見てみましょう。

ここで、開始ノードは1です。ただし、ノード4に進んだ後、サイクル4 – 5 – 6 – 7 – 8 – 9 –4に入ります。次に、ノード9から次のノードに到達した後、このサイクルを再開します。さらに、は存在しないため、リンクリストの最後に到達することはありません。私たちの目標は、ノード4をサイクル開始ノードとして返すことです。

3. うさぎとカメ

この問題を解決するのに役立つアルゴリズムがいくつかあります。たとえば、HashSetを使用できます。各ステップで、現在のノードがセットに存在するかどうかを確認します。含まれている場合は、サイクルの開始ノードになります。そうでない場合は、このノードを set に追加して、次のノードに移動する必要があります。このようなソリューションの時間計算量はです。ただし、スペースの複雑さもです。

時間を使用する別の解決策があります。ただし、定数メモリを使用するため、スペースの複雑さをに減らすことができます。これはフロイドのうさぎと亀のアルゴリズムです。これは、高速および低速のポインターを使用してサイクル開始ノードを見つけるポインターアルゴリズムです。。

3.1. アルゴリズムのアイデア

2つのポインタがあると仮定します。 1つのポインタが別のポインタより2倍速く移動します。この爬虫類の遅いことでよく知られているので、遅いポインターはカメと呼ばれます。一方、より速いポインタはうさぎと呼ばれます。この図では、カメは緑で表され、ノウサギは赤で表されています。

最初は、リストの開始ノード1にあります。亀は一度に1つのノードを移動します。それどころか、うさぎは1つのノードをスキップして、2倍の速さで移動します。 4回移動した後、うさぎはノード9にいます。しかし、カメはノード4に到達したばかりです。

注意することが重要です、それらは両方とも無限にループし始めます。リストにはサイクルが含まれており、両方ともこのサイクルに入ります。結果として、彼らは間違いなくいつか会うでしょう。しかし、私たちは彼らが出会う前の期間に興味があります。これは、アルゴリズムの時間計算量に影響を与えます。さらに、サイクルの長さであるステップの後に、それらが最大で出会うことを証明します。それはまた、カメが最初の会合の前にサイクル全体を完了しないことを意味します。

3.2. 説明

アルゴリズムの最初の部分は単純です。私たちの動物はに出会うまで動き始めます。ウサギとカメの別々の軌道は次のとおりです。

それらが同時に移動する場合、6つのステップを実行した後、ノード7で両方が1サイクルで合流します。

アルゴリズムの2番目の部分も単純です。 うさぎを開始位置に移動し、速度を2回下げます。だから、今では亀と同じ速度になっています。 亀は現在の位置から動き続けます。次に、再び出会うまで動き始めます。興味深い事実：彼らは私たちの問題への答えであるサイクルエントリーポイントで会うでしょう。その後、このノードを返し、アルゴリズムを終了します。

次のセクションで、サイクルが開始するノードでそれらが再び会うことを証明します。さて、うさぎをリストの最初に置き、カメと一緒にどこで出会うか見てみましょう。

ご覧のとおり、私たちの動物はノード4で出会います。これは、まさにサイクルの始まりです。

4. フロイドのアルゴリズムの証明

証明はアルゴリズムよりも少し難しいですが、直感的にわかります。証明を3つの部分に分割します。

4.1. 初対面

まず、移動を開始した後に会うことを示しましょう。明らかに、彼らは周期的に会うでしょう。サイクルの長さがであると仮定します。亀がサイクルに入るとき、髪はすでにその位置でサイクルに入っています。これで、別の座標系に移動できます。うさぎと亀の速度を1つ下げます。これで、カメは移動せず、ウサギは1単位時間あたり1ノードの速度で移動します。それらの間にノードがあります。うさぎは段階的に亀に到達します。

彼らの本当の速度について考えてみましょう。うさぎは亀の2倍の速さで動きます。したがって、上記の速度変換は同じ状況をシミュレートすることを意味します。

4.2. 直感的な説明

これで、位置でループ内の最初のミーティングポイントができました。アルゴリズムによると、うさぎの速度を落とし、リストの最初に移動する必要があります。そして、彼らが再び会うとき、会う場所はサイクル開始ノードになります。

開始ノードからループ入口までのリストの長さであると仮定します。サイクルの長さも考えてみましょう。ノウサギとカメはループのノードで出会う。からまでの距離とします。そして、からの距離にしましょう：

さらに、証明します。これは、サイクルの開始時にポインターが一致する理由を説明するのに役立ちます。

で会った後、同時に動き始める前に、リストの最初にうさぎを移します。亀はループを作り、再び現れます。サイクルの最初に到達するための手順を実行する必要があります。覚えておくべき重要なことは、ウサギの速度を亀の速度と同じになるように下げることです。したがって、ウサギは、カメと同じように、サイクルの開始からステップを実行し、その後、サイクルの開始までステップを残します。 ただし、が定数値である場合にのみ機能します。

4.3. 正式な証明

ここで、はモジュロ演算であることを証明します。これは単に、で除算できることを意味し、除算後の余りはZになります。これは、動物がで再び会うことを証明するのに役立ちます。の場合、前のサブセクションで説明した動物の動きを再現できます。想像してみてください、距離Mは非常に長いかもしれません。証明することで、それを示します。

動物が最初に出会う前に、ウサギの距離はになります。は定数値です。が非常に長い場合、ウサギはカメを待つサイクルで多くのループを作ります。一方、亀の距離はです。カメがノウサギの2倍遅い場合は、平等を補うことができます。

、また。に等しい。覚えておくことが重要です、それ。

したがって、、または。

平等の両側をとると、私たちは得ます。

最後に、それを証明しました。これは、フロイドのアルゴリズムが機能することを意味します。

5. 時間とメモリの複雑さ

お気づきのように、一定のスペースの複雑さを使用します。これは、ウサギとカメの2つのポインターにすぎません。

アルゴリズムの時間計算量はです。ここで、はリスト内のノードの数です。時間計算量は線形であり、ポインターが最初に出会う前にポインターを使用してステップを実行するだけの場合に備えて。はサイクルの長さであり、。したがって、最初の部分には時間がかかります。アルゴリズムの2番目の部分も手順を実行します。したがって、最終的な時間計算量はです。

6. 結論

この記事では、リンクリストからサイクル開始ノードを見つける方法について説明しました。さらに、この問題を解決するための最も効率的なアルゴリズムを説明し、証明しました。さらに、証明について直感的に説明しました。 2ポインターアプローチは一般的な手法であり、多くのアルゴリズムの問題で使用できます。たとえば、同じウサギとカメが配列内の重複番号を見つけるのに役立つ場合があります。