アルゴリズム | ダブルポインタはリンクリストを破る優れた魔法の武器です

今は少し理解できました。面接の過程で、面接官が私たちにコードを手書きで書くように頼むことがあります。実際、それは主に私たちの基本的なスキルをテストし、一般の人々に馴染みのある分野を通して私たちの体系的な思考と対処のアイデアを評価するためです。

前回の記事では、基本的なデータ構造であるリンクリスト（単一リンクリスト）について学びました。次に、LeetCode から興味深いアルゴリズムの問​​題をいくつか選択して、皆さんと一緒に学習します。

リンク リストが相対位置に関連している場合は、1 回のトラバーサルで二重ポインタ (高速ポインタと低速ポインタ) を導入することで解決できます。

1. 単方向リンクリストにループがあるかどうかを検出する

トピック: 指定された単一リンク リストが与えられた場合、ループがあるかどうかを判断してください。

アルゴリズムの初心者である私がこの質問を見ると、何も考えずに思い浮かぶアイデアは、HashSet を導入し、単一リンク リストを最初からトラバースして、各要素を HashSet に格納することです。トラバース プロセス中に、HashSet 内のノードに要素が存在する場合、ストレージ ループを示します。

注意: この記事のリンク リストは、上記の著者が作成したリンク リストを使用しています。

コードは次のように実装されます。

アルゴリズムの分野では、アルゴリズムの長所と短所を評価する際に、通常、時間の複雑さと空間の複雑さという 2 つの側面があります。

• 時間の計算量: O(N)。リンク リスト全体を走査する必要があるためです。リンク リストのデータが大きくなるにつれて、走査回数が増加します。
• 空間計算量: O(N)。走査されたノードを格納するために追加のスペースが必要になるためです。

上級: 上記のアルゴリズムを最適化して、空間計算量を O(1) に減らすことはできますか?

業界には古典的なアルゴリズムであるウサギとカメのアルゴリズムがあり、これは主にリンクリストにループがあるかどうかを検出するために使用されます。通常、次の問題を解決できます。

• リンクリストに循環があるかどうかを確認する
• リングがある場合は、リングのエントリノードを計算する
• 周期がある場合は、周期の長さを計算する

「ウサギとカメ」の詳しい説明はインターネットから入手できます。

ウサギとカメのアルゴリズムの理論 1: 2 つの高速ポインタと低速ポインタを導入します。両方のポインタは、リンク リストのヘッド ノードから同時にトラバースを開始します。高速ポインタは毎回 2 ステップ移動し、低速ポインタは毎回 1 ステップ移動します。リンク リストにループが格納されている場合、高速ポインタは最終的に低速ポインタに追いつきます。つまり、2 つのポインタが重なります。

次に、このルールに従ってサンプル コードを次のように記述します。

とてもエレガントですね。必要なのはポインター 2 つだけです。

ウサギとカメのアルゴリズムの理論 2: 高速ポインタと低速ポインタが初めて出会った後、リングへの入口が必要な場合、方法は次のようになります。低速ポインタをキューの先頭に移動し、高速ポインタと低速ポインタが初めて出会ったポイントがリングの入口ノードになります。

2. リンクリストの最後のn番目のノードを削除する

「ウサギとカメのアルゴリズム」を理解する前は、最後の n 番目のノードを削除するには、必ずリンク リストを 1 回走査し、len で表されるリンク リストの合計長さを取得してから、もう一度走査します。2 回目の走査では、(len-n) 個のノードを走査するだけで済みます。

しかし、ウサギとカメのアルゴリズムを学んだ後では、読者も 2 つのポインタを導入することで、1 回の走査のみが必要になると考えることができると思います。

具体的な解決策は次のとおりです。

2 つのポインタが導入されます。初期状態では、両方とも Header ノードを実行します。次に、1 つのポインタが n 回移動され、その後、最初のポインタがリンク リストの最後に到達するまで、両方のポインタが同時に移動されます。このとき、2 番目のポインタは最後から n 番目のノードです。上図に従って、最初のポインタがキューの最後尾に移動したときの状態図は次のようになります。

これは具体的なコードの書き方に関係します。上図に示すように、最後から n 番目のノードが削除され、単一のリンク リストであるため、通常は最初に削除するノードの前のノードを見つける必要があります。この観点から、上記の終了条件の最初のタイプの方が適切です。以下は、上記のアイデアに基づいたコード実装です。

コードは次のように解釈されます。

コード @1: 現在のノードが空でない限り、後方へ移動し続けることができます。これは主に、ノードがちょうど n 個ある場合に n 回移動できることを保証するためです。また、理解しやすいです。たとえば、現在 3 つのノードのリンク リストがあります。下から 3 番目のノードを削除する場合、その実行軌跡は次の図のようになります。

コード @2: i が n 未満の場合、n 回のトラバーサルが実行されず、要素が欠落し、配列の範囲外例外が直接スローされることを意味します。

コード @3: 上の図に示すように、ツリーが正確に n 回走査され、ヘッド ノードが直接削除されることを意味します。

コード @4: 次に、最初のポインタと 2 番目のポインタが同期してプッシュされます。単一のリンク リストはノードを削除するため、削除されたノードの前のノードを知る必要があります。そのため、次の図に示すように、最初のポインタは末尾のノードを指します (node.next == null、末尾に到達したことを示します)。

これでコード解釈は終わりです。ダブルポインタの威力には感心せざるを得ません。

3. リンク リストの中間ノードを見つけます。上記の 2 つの質問の説明とトレーニングの後、読者はリンク リストの分野でこのような位置関連の質問と、究極の必殺武器であるダブル ポインターを目にすることになると思います。

解決策: 中間位置に 2 つのポインタを導入します。高速ポインタは低速ポインタの 2 倍の速度であるため、高速ポインタがリンク リストの末尾に到達すると、低速ポインタはリンク リストのちょうど真ん中に位置します。