読者です 読者をやめる 読者になる 読者になる

したいことだけする

プロのプログラマになるまでの記録を書いていきます

フロイドの循環検出アルゴリズム

アルゴリズム c言語

任意の連結リストの中にループがあるかどうか。あればループが開始するノードを見つけよ。
ってときフロイドの循環検出アルゴリズムを使う。(ウサギとカメのアルゴリズム

1度に1動く低速のポインタと1度に2動く高速のポインタでリストを横断させる。
もしもリストの中にループがあれば、ループの中で高速のポインタが低速のポインタに追いつく。
ループがなければ高速のポインタはリストの最後まで横断することができる。(nextがNULLのノードにたどり着く)

ここまではすんなりと理解できた。理解に時間がかかったのはこの後のループが開始するノードを見つけるとき。

ループの中で高速のポインタが低速のポインタに追いついたら、どちらかのポインタをリストの先頭に移動させる。
ここでは高速のポインタを移動させる。
その後両方のポインタを1ずつ動かして、両者の出会う位置がループの開始ノードである。

どうして先頭に戻して1ずつ動かしてもう一回出会った点がループの開始ノードなのか?
手元にあった図をたどってみると確かにそうなったがどうしてかはすぐに分からなかった。

特定のパターンではなく、図のように抽象化して考えてみる。

f:id:shimahide:20160330081437p:plain

A点はループの開始ノード、B点は低速ポインタがA点にいるとき高速ポインタがいるノード、C点は両者のポインタが出会うノードの位置とする。
先頭からループの開始点までの距離を λ、A点とB点の距離を μ、リストの長さを L とする。

低速ポインタがA点にたどり着いたとき、高速ポインタはB点にいる。2点の距離は μ 。まぁそう定義したので。。。
リストの長さが L なので、高速ポインタが低速に追いつくためには L - μ だけの距離を追いつかなければならない。
低速ポインタが1進むごとに1差が縮まっていくので、低速ポインタがA点から L - μ 動いた点で両者のポイントが出会う。このノードの位置がC点。
つまりC点とA点から L - μ 進んだ位置にあり、リストの長さは L なので L - ( L - μ ) = μ となり、C点からA点の距離は μ となる。
少し話を戻して、最初に低速ポインタがA点にたどり着いたとき低速ポインタは先頭から λ だけ移動している。高速ポインタは 先頭から2λ 移動している。
すなわち、高速ポインタはA点からλ移動したノードの位置がC点になる。
L > μ のときは、λ = μ となる。
L < μ のときは、L を λ で割った余りが μ となる。(ループなのでグルグル回って何周かした余りがμ)
とにかく、ループの長さ L のループ上で λ 進むとループをグルグル回るにしろ回らないにしろ、最初の位置から μ 先のノードの位置に移動することとなる。
ここで、λ は先頭からループ開始ノードの位置A点までの距離であり、2点のポインタが出会ったノードの位置C点からA点までの距離が μ なので、先頭から λ 進んでもA点に、C点から λ 進んでもA点にたどり着く。なので、
高速のポインタが低速のポインタに追いついた後、どちらかのポインタを先頭に移動させてその後両者を1ずつ進めて出会った点がループの開始ノードの位置になる。

ミソはリスト内を λ 進んだら周回してもしなくても μ 移動するというとこ。

最後にソースコードものせておきます。

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

ListNode *FindBeginOfLoop ( ListNode *head ) {
    ListNode *fast = head, *slow = head;

    //高速ポインタが低速ポインタに追いつくかリストの最後に到達するまでリストを横断
    do {
        fast = fast -> next;
        if (fast != NULL) {
            // 高速ポインタは2つずつ進む
            fast = fast -> next;
        }
        // リストの最後までいったのでループはなし
        else {  
            return NULL;
        }
        // 低速ポインタは1つずつ進む
        slow = slow -> next;
    } while ( fast != slow );

    //高速ポインタを先頭に移動させる
    fast = head;
    do {
        //両者を1つずつ進ませる
        fast = fast -> next;
        slow = slow -> next;
    } while (fast != slow);

    return fast;
}