フロイドの循環検出アルゴリズム（ウサギとカメ）で連結リストのサイクルを検出する方法

フロイドの循環検出アルゴリズム（Floyd's Cycle Detection Algorithm）は、単方向連結リスト内に循環（ループ）が存在するかどうかを検出するための代表的なアルゴリズムの一つです。「ウサギとカメ（Hare and Tortoise）」アルゴリズムとも呼ばれ、2つのポインタを活用することで、追加のメモリをほとんど使わずに効率的にサイクルの有無を判定できます。

このアルゴリズムでは、最初に2つのポインタ（ウサギとカメ）がどちらもリストの先頭ノード（ヘッド）を指します。イソップ寓話の「ウサギとカメ」の物語と同じように、ウサギはカメの2倍の速さで進みます。そのため、ウサギが道の終わりに到達する頃には、カメはちょうど道の中間地点に到達している、というイメージです。

アルゴリズムの手順

1. ウサギとカメの両方のポインタを、リストの先頭ノードで初期化します。

2. ウサギはカメの2倍の速さで移動します。

3. ウサギとカメを移動させ、ウサギが連結リストの終端に到達した場合は、リストにループが存在しないと判断して処理を終了します。

4. 終端に達しない場合は、ウサギとカメの両方を前へ進めます。

5. ウサギとカメが同じノードに到達した場合、リスト内に循環（サイクル）が存在することが確定するため、処理を終了します。

6. それ以外の場合は、手順2に戻って処理を繰り返します。

アルゴリズムの擬似コード

tortoise := headNode
hare := headNode
foreach:
    if hare == end
        return 'There is No Loop Found.'
    hare := hare.next
    if hare == end
        return 'No Loop Found'
    hare = hare.next
    tortoise = tortoise.next
    if hare == tortoise
        return 'Cycle Detected'

計算量と特徴

このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)です。ハッシュセットなどで訪問済みノードを記録する方法と異なり、追加のメモリを必要としないため、メモリ効率が求められる場面で特に有効です。

また、サイクルの検出後、カメを先頭に戻して両ポインタを同じ速度で進めると、2つのポインタはサイクルの開始ノード（循環の入口）で出会うことが数学的に証明されています。この性質を利用すれば、サイクルの有無だけでなく、その開始位置も特定できます。