ウサギとカメ(循環リスト)
連結リストで循環しているかどうか、どこで循環が始まっているのかを検出する。
正式には、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; }