フロイドの循環検出法 external_link

リスト構造上にある循環路を検出する方法。
※ハッシュ表を使う方法もある。 → 入門データ構造とアルゴリズム p383 Q14ー9

考え方

循環の検出

1. ノード０をスタート地点とし、兎ポインタが２つ移動する間に、亀ポインタを１つ移動させる。

2. 兎が1周した時、亀はまだ半周。

3. 亀が1周すると兎は2周し亀と出会う。
   この出会いが「循環」であることを証明する。
   ※「循環」でなければ、兎は亀に出会うことなく出口に到着する。

循環路の入り口検出

1. ノード０を引っ張り出す。このとき循環路の長さは変わらないものとすると、兎と亀はノード６で出会う。

2. 兎はそのままにして亀をノード０へ戻す。そして、今度は兎と亀を同じ速度（１つずつ）で移動させる。
   兎と亀は循環路の入り口で出会う。
   今回は１ノードだけ引っ張り出したがいくつ引っ張り出しても結果は同じである。

擬似コード

FindCycle(LIST) {
    head = 0
    turtle = LIST.HEAD
    rabbit = LIST.HEAD
    while (The rabbit has not arrived at the end of the list) {
        turtle = turtle.NEXT
        rabbit = rabbit.NEXT
        rabbit = rabbit.NEXT
        if (turtle == rabbit) {
            // get cycle entrance
            turtle = LIST.HEAD
            while (true) {
                if (turtle = rabbit) return rabbit
                turtle = turtle.NEXT
                rabbit = rabbit.NEXT
            }
        }
    }
    return no-cycle
}

🌏 Map

same layer	lower layer