Floyd のウサギとカメを使ってサイクルを検出するにはどうしますか?

Question

Accepted Answer

**Floyd's cycle detection** は、異なる速度で動く 2 つのポインタを使用して、シーケンス (リンクリストなど) のループを検出します。サイクルが存在する場合、高速ポインタは遅いポインタに追いつきます。**O(1)** の追加空間を使用します。

## アイデア

**slow** ポインタを 1 ステップ、**fast** ポインタを 2 ステップ動かします。サイクル内では、ギャップが毎ステップ 1 ずつ縮まるため、必ず衝突します。サイクルがない場合、fast ポインタが終端に到達します。

## 例

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## 計算量

- **時間:** O(n)。**空間:** O(1)。

ハッシュセットアプローチも機能しますが、O(n) の空間がかかります。Floyd のアルゴリズムは定数空間を使用します。

## 使用場面 / 落とし穴

**リンクリストのループ検出**、サイクルの開始地点の検出、関数グラフ (各ノードが 1 つの後続ノードを持つ) でのサイクル検出に使用します。null 参照を避けるため、常に `fast.next` をガードしてください。一般的なグラフの場合は、DFS と再帰スタックを使用します。

## なぜ重要なのか

サイクル検出は安全な走査に不可欠です。検出されないループは無限反復を意味します。

Floyd のアルゴリズムは、O(n) 空間の問題を巧妙な不変量で O(1) 空間で解く美しい例です。

リンクリストのインタビューや、状態機械と数列の無限ループ検出に出現します。