リンクリストのサイクル検出
末尾のノードの next が、うっかりリストの途中を指してしまうことがあります。見た目はいつものリストです。ところが、たどり始めると二度と終わりません。
たどり始めたら、いつまでも終わらない
Python
cur = head
while cur is not None:
print(cur.value)
cur = cur.nextこのループは next が空になった時点で止まります。途中のノードへ戻る札が 1 枚でもあると、その先はぐるぐる回り続け、空には永久に届きません。ログが出続けるか、無言のまま固まるかのどちらかです。輪があるかどうかを、たどる前に知りたくなります。
速さの違う 2 つを走らせる
対処法は少し変わった形をしています。同じ先頭から 2 つの目印を出し、片方は 1 歩ずつ、もう片方は 2 歩ずつ進めます。
Python
def has_loop(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False輪が無ければ、速いほうが先に末尾を突き抜けて while が終わります。輪があれば、2 つは必ず同じノードで重なります。追加で使うメモリは、変数 2 つぶんだけです。
なぜ必ず追いつくのか
輪に入るまでの間は、2 つの差はどんどん開いていきます。ただ、速いほうが先に輪へ入るので、遅いほうが輪に着いたときには、相手はすでに輪の中を回っています。ここから先が本番です。
2 つとも輪の中に入ってしまえば、あとは追いかけっこです。1 回進むごとに、速いほうは 2 マス、遅いほうは 1 マス動くので、2 つの差はちょうど 1 マスずつ縮みます。
縮み方が 1 ずつなので、差が 0 を飛び越えることはありません。輪の長さを L とすれば、遅くとも L 回以内に差は 0 になり、2 つは同じノードに立ちます。これが「必ず出会う」の中身です。
速いほうを 3 歩にすると壊れます。差は 2 ずつ縮むので、L が偶数で差が奇数のときは 0 を素通りし、いつまでもすれ違い続けます。1 歩と 2 歩という組み合わせに意味があるわけです。
輪ができるのはリストだけではありません。モジュールの import が A から B、B から A と戻っていれば、依存をたどるビルドツールは同じところを回り続けます。だから依存を解決する側には、たいてい輪の検出が組み込まれています。たどる前に輪を疑う、という発想はどのデータ構造でも同じです。
訪れた場所を全部記録しておいて、2 度目に来たら輪あり、と判定する手もあります。分かりやすい代わりに、ノード数ぶんのメモリを使います。今回の課題はその記録する側で書きますが、記録の順番だけ気をつけてください。先に記録してから照合すると、必ず自分自身に当たって、どんな入力でも輪ありになります。
要件
- 連結リストは配列 arr で表現する
- 値の重複を hash set で検出し、O(n) で判定する
- 重複があれば true (boolean) を、なければ false を返す
入出力例
hasCycle([1,2,3]) → false
hasCycle([1,2,3,2]) → true
hasCycle([1]) → false
hasCycle([5,5]) → true
hasCycle([1,2,3,4,5]) → false
hasCycle([1,2,3,4,3]) → trueヒント
