リンクリストのサイクル検出｜コードで実践

リンクリストのサイクル検出

このレッスンで分かること

Set を使うことで has と add が O(1) で実行でき、全体として O(n) で判定できます

連結リストには サイクル (循環) が含まれる可能性があります

本コースでは配列表現を使うため、サイクル付きリストを別の形で表現します

リンクリストのサイクル検出とは

Floyd の Tortoise and Hare アルゴリズムを使って連結リストのサイクル有無を判定する。

連結リストには サイクル (循環) が含まれる可能性があります。本来 null で終わるべき末尾ノードの next が、リストの途中のノードを指してしまうケースです。サイクルがあると、while node: node = node.next で辿るとループが永遠に終わりません。サイクルを検出することは、無限ループ防止の基本テクニックです。

本コースでは配列表現を使うため、サイクル付きリストを別の形で表現します。具体的には、サイクルがあるリストを「最初の数要素 + 同じ要素の繰り返し」とみなして、[1, 2, 3, 2, 3, 2, 3] のように重複した連続パターンが現れる配列をサイクルありと判定します。簡易版として、本レッスンでは各ノードの値が一意であるリストを前提に「重複する値が出現したらサイクルあり」と定義します。値が本来から重複しているリストには適用できない擬似表現である点に注意してください。

本物のサイクル検出は Floyd の Tortoise and Hare が定番。亀 (1 歩) と兎 (2 歩) を走らせて出会えばサイクル。

Floyd のアルゴリズム

本物のリンクリストでサイクル検出するときの標準アルゴリズムは Floyd のサイクル検出 です。2 つのポインタ slow と fast を用意し、slow は 1 歩、fast は 2 歩ずつ進めます。サイクルがあれば必ず fast が slow に追いつき、なければ fast が null に到達します。

サイクルが存在すれば、亀と兎は必ずどこかで出会う。サイクル内では fast が slow に対して毎ステップ相対距離を 1 ずつ縮めるため、サイクル長 L 以内に距離が必ず 0 になるからです。

ビジュアルで理解する

diagram (will load when visible)

図のポイント (テキスト併記)

図のように、ノード 4 の next がノード 2 を指していると、2 -> 3 -> 4 -> 2 -> 3 -> 4 -> ... と無限ループになります

図のように、ノード 4 の next がノード 2 を指していると、2 -> 3 -> 4 -> 2 -> 3 -> 4 -> ... と無限ループになります。これをサイクルと呼びます。

Python での実装

配列表現では、set を使って訪問済みの値を記録するシンプルな方法を採用します。

Python

def hasCycle(arr):
    seen = set()
    for value in arr:
        if value in seen:
            return True
        seen.add(value)
    return False

本物のリンクリストでは「同じノードに 2 回到達したらサイクル」と判定するため、set にノード ID を入れて確認します。本コースでは配列の値の重複でサイクルを擬似的に表現します。

JavaScript での実装

JavaScript

function hasCycle(arr) {
  const seen = new Set();
  for (const value of arr) {
    if (seen.has(value)) {
      return true;
    }
    seen.add(value);
  }
  return false;
}

Set を使うことで has と add が O(1) で実行でき、全体として O(n) で判定できます。配列 を使った O(n^2) 版より高速です。

よくある間違い

1 つ目は 空配列の扱い です。空リストにはサイクルがないので False を返します。seen を空集合で初期化していれば自然に対応できます。2 つ目は 値を追加するタイミング です。seen.add(value) を先にやってから if value in seen でチェックすると、自分自身にヒットして常に True になってしまいます。必ず チェック → 追加 の順です。3 つ目は 本物の Floyd 法と混同 することです。本コースでは値の重複でサイクルを判定していますが、本物のリンクリストでは slow / fast の 2 ポインタを使うことを覚えておきましょう。

やってみよう

[1, 2, 3] を渡したらサイクルなしで False が返るか確認する。
[1, 2, 3, 2] を渡したら値 2 が重複しているので True が返るか確認する。
本物のリンクリストで Floyd の Tortoise and Hare を書いてみる。slow = head; fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next; if slow == fast: return True の形になる。

Hash 法 vs Floyd 法

hash set を使う方法は分かりやすく、O(n) 時間で済みますが、O(n) 空間を消費します。一方 Floyd のサイクル検出 は O(n) 時間 / O(1) 空間で済むのが強みです。技術面接では「空間計算量を O(1) に抑えろ」という追加要件がよく出るので、Floyd 法を覚えておくと有利です。

Floyd 法の正しさの直感は次のようなものです。サイクルがあるとき、slow がサイクルに入った時点で fast も同じサイクル内にいます。fast は slow より毎ステップ 1 つだけ進むため、サイクル長を L とすれば、最大 L ステップ以内に必ず追いつきます。サイクルがなければ fast が先に null に到達するため、ループは安全に終わります。

Floyd 法は O(1) 空間。技術面接では 空間を抑えろ と要求されるので覚えておこう。

実務での応用

サイクル検出は無限ループの未然防止だけでなく、関数の依存グラフ で循環参照を検出する場面でも使われます。Webpack のような JS バンドラーは、ファイル間の import 関係をグラフとして辿りますが、A -> B -> A のような循環があると無限ループになるため、こうした検出ロジックが内部に組み込まれています。データベースの外部キー制約でも、自己参照的なテーブル設計だと同じような循環チェックが必要になります。

循環検出は 依存グラフ の解析でも頻出。Webpack や package manager の内部でも実装されている。

サイクル検出は無限ループ防止の基本。hash set か 2 ポインタ法 を覚えておけば実務でも応用が効く。

よくある質問

Q. リンクリストと配列はどう使い分けますか？

A. 配列はランダムアクセス O(1)、リンクリストは先頭への追加 O(1) が強みです。ほとんどの実用ケースで配列の方が速く、リンクリストはアルゴリズム問題の練習や特殊用途（OS のスケジューラ等）で使われる程度です。

Q. サイクル検出はどう実装しますか？

A. Floyd の循環検出（2 ポインタ法、tortoise and hare）が定番です。slow を 1 ステップ、fast を 2 ステップ進めると、ループがあれば必ず同じノードで出会います。空間 O(1) で動くのが優秀な点です。

Q. リンクリストを反転するコツは？

A. prev, curr, next の 3 ポインタを使い、curr.next = prev で 1 個ずつ繋ぎ替えます。再帰版でも書けますが、反復版の方がスタック消費が無く安全です。LeetCode の Reverse Linked List が定型問題なので解いておくと良いです。

次のレッスン

次は ソート済みリンクリストの merge で、Floyd の Tortoise and Hare アルゴリズムを使って連結リストのサイクル有無を判定するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

サイクル検出の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. サイクル検出とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

リンクリストのサイクル検出