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

ウサギとカメ(循環リスト)

連結リストで循環しているかどうか、どこで循環が始まっているのかを検出する。
正式には、Floyd's cycle-finding algorithmと呼ぶらしい。
証明は省くが、だいたい↓のような手順

循環判定

・セルを2つづつ移動するのをウサギ、1つづつ移動するのをカメとして、1ステップずつシミュレートする。
・ウサギとカメが出会う(同じセルにいる)場合そのリストは循環している。

循環場所の検出

・ウサギを最初のセルにもどし、ウサギのスピードを1にする。
・再度シミュレートして、ウサギとカメが出会ったセルが循環のスタート地点。

コード

hare:ウサギ
tortoise:カメ

is_circle_listは、循環リストなら循環スタートのセルを返し、そうでなければfalseを返す。

var Cell = function(a,b){
    this.car = a;
    this.cdr = b;
}

var is_circle_list = function(ls){
    var hare = ls;
    var tortoise = ls;
    while (true){
        if (hare.cdr == null || hare.cdr.cdr == null){
            return false;
        }
        hare = hare.cdr.cdr;
        tortoise = tortoise.cdr;

        if (hare == tortoise){
            break;
        }
    }
    
    hare = ls;
    while (true){
        if (hare == tortoise){
            break;
        }
        hare = hare.cdr;
        tortoise = tortoise.cdr;
    }
    return hare;
}