アルゴリズム - 5. 高速・低速ポインタ

高速・低速ポインタを使う場面

高速・低速ポインタは、異なる速度で連結リストを探索してパターンを検出したり、特定の位置を見つけたりする必要がある場合に使用します。サイクル検出に最も一般的に使用されますが、以下の用途にも適応できます：

サイクル検出（クラシックな使用例 - Floydのサイクル検出）
連結リストの中間ノードを1パスで見つける
連結リストのサイクルの開始点を見つける
末尾からk番目のノードを検出する（ギャップを維持することで）
連結リストの回文配列を見つける
異なる速度で位置を比較することで隠れた構造を明らかにする問題

例題

欠陥のある製造ライン：工場の円形コンベアベルトで、製品が一列に移動している様子を想像してください。トラックの欠陥により、一部の製品が以前の地点にループバックする可能性があります。

生産ライン上の製品を表す連結リスト：1 → 2 → 3 → 4 → 5 → 3（ループバック）において、次を判定してください：

生産ラインにループはありますか？
ループはどこから始まりますか？

答え：はい、ループがあり、ノード3から始まります。

最も重要な洞察

異なる速度での移動はサイクル内での出会いを保証する - 2つのポインタが連結リストを横断し、一方が他方の2倍の速度で移動する場合、サイクル内で最終的に出会い、サイクルが存在しない場合は自然に終端で停止します。

メンタルノート：アルゴリズムの天才性は速度差にあります。高速ポインタは低速ポインタが1ステップ移動する間に2ステップ移動します。サイクル内では、これにより高速ポインタが低速ポインタに予測可能な速度で追いつく「追跡」が生じます。サイクルがない場合、高速ポインタは単に最初に終端に到達します。この単純な速度差が余分なメモリなしでサイクル構造を明らかにします。

意思決定フレームワーク

トラバーサルの各ステップで、アルゴリズムは以下の単純なチェックを行います：

高速ポインタは終端に到達したか？（nullまたはnextがnull）→ サイクルは存在しない
高速と低速のポインタは同じノードを指しているか？ → サイクル検出
上記のいずれかの条件が満たされるまで異なる速度で移動を続ける

コード

連結リストの中央を見つける

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

// 2つのポインタで連結リストの中央を見つける。
// 時間: O(n)、空間: O(1)
function middleOfList(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // 意思決定フレームワーク：高速ポインタが終端に到達するまで続ける
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // slowPointerを条件に含めることで、TypeScriptが両方がnullでないことを理解するのに役立ちます
    // 注：論理的にfastPointerがnullでない場合、slowPointerもnullではありません
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;
    // 高速ポインタを2ステップ前進
    fastPointer = fastPointer.next.next;
  }

  // 高速が終端に到達したとき、低速は中央にある
  return slowPointer;
}

// 使用例：
// リスト: 1 → 2 → 3 → 4 → 5
// 高速が5にあるとき、低速は3（中央）にある

サイクルが存在するかの検出

// 連結リストにサイクルが含まれているか判定する。
// 時間: O(n)、空間: O(1)
function hasCycle(head: ListNode | null): boolean {
  let slowPointer = head;
  let fastPointer = head;

  // 意思決定フレームワーク：ポインタが出会うか高速が終端に到達するまで続ける
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // slowPointerを条件に含めることで、TypeScriptが両方がnullでないことを理解するのに役立ちます
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;

    // 高速ポインタを2ステップ前進
    fastPointer = fastPointer.next.next;

    // ポインタが出会ったかチェック（サイクル検出）
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      return true;
    }
  }

  // 高速ポインタが終端に到達 - サイクルは存在しない
  return false;
}

// 使用例：
// サイクルありのリスト: 1 → 2 → 3 → 4 → 5 → 3（ループバック）
// 結果: true

サイクルの開始点を見つける

// 連結リストにサイクルが含まれているか判定し、
// サイクルの開始点を返す。そうでなければnullを返す。
// 時間: O(n)、空間: O(1)
function cycleStart(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // フェーズ1：異なる速度を使用してサイクルの存在を検出
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    slowPointer != null
  ) {
    // ループ条件からTypeScriptはslowPointerがnullでないことを理解
    slowPointer = slowPointer.next;

    // 高速ポインタを2ステップ前進
    fastPointer = fastPointer.next.next;

    // サイクル内でポインタが出会ったかチェック
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      break; // サイクル検出、フェーズ2へ進む
    }
  }

  // サイクルが存在しないために終了したかチェック
  const fastPointerReachedEnd = fastPointer == null || fastPointer.next == null;
  if (fastPointerReachedEnd) {
    return null;
  }

  // フェーズ2：サイクルの正確な開始点を見つける
  // 数学的性質：ヘッドからサイクル開始点までの距離は
  // 出会い地点からサイクル開始点までの距離（サイクルを前進する場合）と等しい
  // - （詳細は下記のセクションを参照）
  //
  // リストの例: 1 → 2 → 3 → 4 → 5 → 6 → 3（サイクルはノード3から開始）
  //   - 非サイクル部分: 1 → 2（長さ = 2）
  //   - サイクル部分: 3 → 4 → 5 → 6 → 3（長さ = 4）
  //   - 出会い地点: ノード5（低速と高速が最初に出会う場所）
  //
  //   ヘッド（1）からサイクル開始（3）までの距離: 2ステップ
  //   出会い地点（5）からサイクル開始（3）までの距離: 5→6→3 = 2ステップ
  //   これらの距離は常に等しい！

  // 意思決定フレームワーク：1つのポインタをヘッドにリセットし、両方を同じ速度で移動
  let pointerAtMeetingPoint = slowPointer;
  let pointerAtHead = head;

  while (
    pointerAtHead != null &&
    pointerAtMeetingPoint != null &&
    // 両方のポインタがサイクル開始点で出会うまで続ける
    pointerAtMeetingPoint != pointerAtHead
  ) {
    // 両方のポインタを一度に1ステップずつ移動（同じ速度）
    const nextPositionFromHead = pointerAtHead.next;
    pointerAtHead = nextPositionFromHead;

    const nextPositionFromMeeting = pointerAtMeetingPoint.next;
    pointerAtMeetingPoint = nextPositionFromMeeting;
  }

  // 両方のポインタは今サイクル開始点を指している
  return pointerAtHead;
}

// 使用例：
// リスト: 1 → 2 → 3 → 4 → 5 → 3（ノード3がサイクル開始）
// 結果: 値3のノード

フェーズ2が機能する理由：数学的証明

重要な性質：高速と低速のポインタがサイクル内で出会うとき、ヘッドからサイクル開始点までの距離は、出会い地点からサイクル開始点までの距離（サイクルを前進する場合）と等しい。

記法

定義：

L = 非サイクル部分の長さ（ヘッドからサイクル開始点までの距離）
C = サイクルの長さ
k = サイクル開始点から出会い地点までの距離（サイクルに沿って測定）

フェーズ1（検出）で何が起こるか

ポインタが出会うとき：

低速ポインタが進んだ距離: L + kステップ（サイクルに入るためのL、出会い地点までのk）
高速ポインタが進んだ距離: 2(L + k)ステップ（2倍の速度で移動）

高速ポインタはサイクル内にあるため、その位置は次のようにも記述できます：

高速が進んだ距離: L + k + nCステップ（nは完全なループの数）

両方が同じ位置にあるため：

2(L + k) = L + k + nC
2L + 2k = L + k + nC
L + k = nC
L = nC - k

重要な洞察

L = nC - kから、距離を理解するために並べ替えることができます：

出会い地点からサイクル開始点まで：

出会い地点はサイクルにkステップ入った位置です（サイクル開始点から）。サイクル開始点に戻るには、サイクルの残りの距離を進む必要があります：

サイクルの残り距離: C - kステップ前進
しかし、L = nC - kであることを証明しました

nC - kを代数的に分解：

なぜnC - k = (完全なループ) + (残り距離)と書けるのか？

除算を使って理解しましょう：

nC - kステップ進む場合：
  nC - k = n × C - k
         = n × C - k - C + C（- C + C = 0なので）
         = (n-1) × C + C - k

この分割が意味を成す理由：
  nC - k = (n-1)C + C - k
         = (n-1)C + (C - k)
           ↑         ↑
      完全な    サイクル開始点
      ループ    までの残り距離

したがって、nC - k = (完全なループ) + (残り距離)

このように考えてください：
- n個の完全なサイクル（nC）があります
- しかしk（サイクル内の位置）を引きます
- これは(n-1)個の完全なループを取り、さらに(C-k)の部分ループを取るようなものです

視覚的表現：
  サイクル内の位置kにいて、nC - kステップ進む必要がある場合：
  - まず(n-1)個の完全なループを行う（位置kに戻る）
  - 次に(C - k)ステップをさらに行う（サイクル開始点に到達）

  これがnC - kが常に(n-1)C + (C - k)に等しい理由です

重要な実現：サイクルでは、nC - kステップを行うことはC - kステップを行うことと同等です。なぜなら、(n-1)Cの部分はサイクルを(n-1)回回って同じ位置に戻るだけだからです。

したがって：

ヘッドからLステップ → サイクル開始点に到達
出会い地点からC - kステップ → サイクル開始点に到達
L = nC - kかつnC - k ≡ C - k (mod C)なので、これらの距離は等しい！

簡単に言えば：ヘッドからLステップ移動することは、出会い地点からC - kステップ移動するのと同じ実際のステップ数を取ります。なぜなら、nC - kの「余分なループ」は円形構造の最終位置を変えないからです。

具体例

リスト: 1 → 2 → 3 → 4 → 5 → 6 → 3（サイクルはノード3から開始）

設定：
- L = 2（サイクル前のノード1、2）
- C = 4（サイクル: 3 → 4 → 5 → 6 → 3）

フェーズ1 - 出会うまでのステップバイステップトレース

ステップ0（開始）：
  低速: [1]      高速: [1]

ステップ1：
  低速: 1 → [2]        高速: 1 → 2 → [3]

ステップ2：
  低速: 1 → 2 → [3]    高速: 1 → 2 → 3 → 4 → [5]
  （低速がサイクルに入る）

ステップ3：
  低速: 1 → 2 → 3 → [4]          高速: 1 → 2 → 3 → 4 → 5 → 6 → [3]
                                 （高速が1周完了）

ステップ4：
  低速: 1 → 2 → 3 → 4 → [5]      高速: 1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → [5]

  ✓ ノード5で出会う！

なぜノード5？

低速はノード5に到達するのに4ステップかかりました
高速はノード5に到達するのに8ステップかかりました（2倍の速度で移動）
低速がステップ2でサイクルに入った後、出会うまでにさらに2ステップ（ステップ3と4）かかりました
高速はすでにサイクルをループしており、ステップごとに1ノードずつギャップを縮めていました

ノード5で出会った後：
- 低速が進んだ距離: 4ステップ（サイクルに入るためのL=2、ノード5までのk=2）
- 高速が進んだ距離: 8ステップ（サイクル開始点まで2、その後6 = サイクルを1.5周）
- k = 2（サイクル開始ノード3から出会い地点ノード5までの距離: 3→4→5）
- 検証: L = nC - k → 2 = 1(4) - 2 ✓

フェーズ2 - サイクル開始点の発見

両方のポインタが同じ速度で移動（一度に1ステップ）：

1つのポインタをヘッドにリセット：
  pointerAtHead: [1]
  pointerAtMeetingPoint: [5]

ステップ1：
  pointerAtHead: 1 → [2]
  pointerAtMeetingPoint: 5 → [6]

ステップ2：
  pointerAtHead: 1 → 2 → [3]
  pointerAtMeetingPoint: 5 → 6 → [3]

  ✓ 両方がノード3（サイクル開始）で出会う！

両方のポインタは正確にL = 2ステップ進み、サイクル開始点に同時に到着しました！

視覚的証明

リスト: 1 → 2 → 3 → 4 → 5 → 6 → 3
      |___L___|_____サイクル____|
              ↑           ↑
          開始(3)    出会い(5)

ヘッドから開始までの距離: L = 2
出会いから開始までの距離: (C - k) = (4 - 2) = 2

L = nC - kで、サイクル内でC - k前進するので：
L ≡ C - k (mod C)

したがって: ヘッドからの2ステップ = 出会い地点からの2ステップ
両方が同時にサイクル開始点に到着！

この数学的性質により、Floydのサイクル検出アルゴリズムは非常にエレガントになります - この距離の等価性により、フェーズ2は必ず機能します。

疑問の解消

よくある疑問：「異なる速度で移動することがサイクル内でのポインタの出会いを保証する理由は？高速ポインタが低速ポインタを飛び越え続けたらどうなる？」

これはFloydのサイクル検出アルゴリズムに関する洗練された懸念です。具体的な推論でそれに対処しましょう。

高速ポインタが低速ポインタを見逃す可能性があると思う理由

連結リスト内のサイクルを考えてください。次のように考えるかもしれません：

「高速ポインタは一度に2ステップ移動し、低速ポインタは1ステップ移動する」
「サイクル内で、高速ポインタは同じノードに着地することなく低速ポインタを飛び越えることができないか？」
「アルゴリズムは出会うことを前提としているようだが、それは実際に保証されているのか？」

この考えが間違っている理由

重要な実現：各反復で、高速と低速のポインタ間のギャップは正確に1ノード閉じます！

相対速度の概念でこれを理解しましょう：

両方のポインタがサイクル内にあるとき：
- 高速ポインタの移動: 反復あたり2ノード
- 低速ポインタの移動: 反復あたり1ノード
- 相対速度（高速が低速に追いつく）: 2 - 1 = 反復あたり1ノード

これは、それらの間の距離が各反復で正確に1ノード減少することを意味します。

具体例：ギャップは常に閉じる

5つのノードを持つサイクルをトレースしましょう。低速が位置0、高速が位置3にあります：

反復0：
サイクル: [0] → [1] → [2] → [3] → [4] → [0]（ループ）
        ↑           ↑
       低速        高速
ギャップ: 3ノード先

反復1：
       [0] → [1] → [2] → [3] → [4] → [0]
              ↑                  ↑
            低速               高速
ギャップ: 2ノード先（1縮小）

反復2：
       [0] → [1] → [2] → [3] → [4] → [0]
                     ↑    ↑
                   低速  高速
ギャップ: 1ノード先（1縮小）

反復3：
       [0] → [1] → [2] → [3] → [4] → [0]
                          ↑
                      低速と高速が出会う！
ギャップ: 0ノード（1縮小）

魔法：初期ギャップサイズに関係なく、各反復で1ずつ減少することは、ギャップが0に達したときに必ず出会うことを意味します！

保証された出会いの数学的証明

長さCのサイクルで：

ポインタ間の初期ギャップ: ある距離D（0 < D < C）
各反復でギャップが減少: 1ノード
出会うまでの反復: D反復

高速ポインタが低速ポインタを「飛び越える」ことができない理由：

反復Nでギャップが2ノードの場合：

N+1反復後、ギャップは1ノードになる
N+2反復後、ギャップは0ノードになる → 出会い

相対速度は常に反復あたり1ノードなので、1回の反復でギャップ=2からギャップ=0に行く方法はありません。

異なるサイクル位置でも機能する理由

ケース1：両方のポインタがサイクル内で開始

各反復でギャップが1縮小 → 保証された出会い

ケース2：ポインタが異なる時間にサイクルに入る

両方がサイクル内にいると、ケース1に戻る
高速ポインタが最初に入り、低速ポインタを待つ
低速が入ると、各反復でギャップが1縮小 → 保証された出会い

Floydアルゴリズムの素晴らしさ

アルゴリズムは3つの重要な性質を活用します：

一定の相対速度：常に反復あたり1ノード
円形構造：ギャップは巡回し、逃げることができない
必然的な収束：Dのギャップは正確にD反復で0に閉じる

この組み合わせにより、サイクル内での出会いが保証され、アルゴリズムをエレガントで確実にします！

もう一つのよくある疑問

よくある疑問：「サイクルが非常に大きい場合 - 10億ノードのような場合はどうなるか？ポインタが出会う前に何十億回もループする必要があり、このアルゴリズムが実用的でなくなるのでは？」

これはFloydアルゴリズムに関する正当なパフォーマンスの懸念です。なぜこの恐れが根拠がないのか調べてみましょう。

巨大なサイクルについて心配する理由

サイクルを持つ巨大な連結リストを考えてください。次のように考えるかもしれません：

「サイクルが10億ノードある場合、ポインタが互いに追いかける必要がある」
「高速ポインタが低速ポインタを何回も周回してから最終的に出会うかもしれない」
「これには何十億回もの反復が必要で、O(n)時間計算量を実際には無意味にする」

この心配が不要な理由

重要な実現：ポインタは、サイクルのサイズに関係なく、最大でも1回の完全なトラバーサル内で出会います！

ここに重要な洞察があります：両方のポインタがサイクル内に入ると、低速ポインタがサイクルの1周を完了する前に出会います。

具体例：必要な最大反復数

最悪ケース分析でこれを証明しましょう：

与えられた条件：
- サイクル長: Cノード
- サイクル内の低速ポインタ位置: 0
- サイクル内の高速ポインタ位置: 1（わずか1ノード先 - 最悪ケース）

反復追跡：
ギャップの開始: C - 1ノード（サイクル内の最大可能ギャップ）
ギャップが縮小: 反復あたり1ノード
出会うまでの反復: C - 1反復

結果: C反復未満で出会う（1完全サイクル未満）

「巨大な」サイクルの実例

10ノードのサイクル（10億ノードのサイクルを表す）をトレースしましょう：

最悪ケースシナリオ：
- サイクル長: 10ノード
- 低速が位置0、高速が位置1
- 最大ギャップ: 9ノード

反復0: 低速=0、高速=1、ギャップ=9
反復1: 低速=1、高速=3、ギャップ=8
反復2: 低速=2、高速=5、ギャップ=7
反復3: 低速=3、高速=7、ギャップ=6
反復4: 低速=4、高速=9、ギャップ=5
反復5: 低速=5、高速=1、ギャップ=4（高速が巡回）
反復6: 低速=6、高速=3、ギャップ=3
反復7: 低速=7、高速=5、ギャップ=2
反復8: 低速=8、高速=7、ギャップ=1
反復9: 低速=9、高速=9、出会う！

総反復数: 9（C-1、C=10）

絶対的な最悪ケースでも、10ノードのサイクルでわずか9回の反復で出会いました！

時間計算量の保証

n個の総ノードを持つ連結リストの場合：

非サイクル部分: 長さLノード
サイクル部分: 長さCノード
合計: n = L + Cノード

フェーズ1（サイクルに到達）：

低速ポインタはサイクルに入るためにLステップ必要
高速ポインタは最大Lステップ必要
反復: L

フェーズ2（サイクル内で出会う）：

低速が入るときの最大ギャップ: C - 1ノード
ギャップは反復あたり1縮小
反復: 最大C - 1

総反復数: L + (C - 1) < L + C = n

これにより、アルゴリズムが**厳密にO(n)**であることが証明されます - 10億ノードのサイクルでも、最大1回トラバースします！

ハッシュセットを使用するよりも優れている理由

訪問済みノードを追跡するナイーブなアプローチと比較してください：

ハッシュセットアプローチ：
- 時間: O(n)
- 空間: O(n) - すべての訪問済みノードを格納

高速＆低速ポインタ：
- 時間: O(n)
- 空間: O(1) - 2つのポインタのみ

10億ノードの場合：
- ハッシュセットには約8-16GBのメモリが必要
- 高速＆低速には約16バイト（2つのポインタ）が必要

数学的な美しさ

最悪ケースシナリオは美しい性質によって制限されます：

最大反復数 = n - 1

ここでnは総ノード数です。これは次を意味します：

100ノード → 最大99反復
1,000ノード → 最大999反復
1,000,000,000ノード → 最大999,999,999反復

「無限にループする」ことはありません - アルゴリズムは入力サイズに線形にスケールする厳格な上限を持ち、巨大なサイクルでも非常に効率的です！