Linked List Cycle
連結リストは配列 next に格納されています。ノード i はノード next[i] にリンクし、-1 はそこでリストが終わることを意味します。先頭はノード 0 です。先頭からリンクをたどり、すでに訪れたノードに戻ってきた場合は true を、末尾に到達した場合は false を返してください。たどっても到達しないノードは、互いにループ状にリンクしていても対象外です。
関数
- nextinteger-array
- 各ノードのリンク: next[i] はノード i の次のノード、または -1 です
- 戻り値boolean
- true はノード 0 からの移動でノードを再訪した場合、false は -1 に到達した場合
制約
1 ≤ next.length ≤ 104-1 ≤ next[i] ≤ next.length-1- 複数のノードが同じノードにリンクする場合があり、headから到達できないノードもあります。
例
- 入力
- next = [1, 2, 3, 1]
- 出力
- true
- 説明
- たどり方は0、1、2、3と進み、その後1に戻ります。ノード1は2回訪問されるため、リストにはノード1、2、3を通るサイクルがあります。
- 入力
- next = [2, -1, 1]
- 出力
- false
- 説明
- 経路は 0、2、1 と進み、その後
-1に到達します。異なるノードを3つ通ってから終点に達するため、サイクルはありません。
- 入力
- next = [-1, 2, 1]
- 出力
- false
- 説明
- Node 0 は
-1にリンクしているため、リストの長さは 1 ノードです。Node 1 と Node 2 はループ状に互いにリンクしていますが、先頭からたどってもそれらには到達しません。
提出時に隠しテスト+16件
発展問題
追加メモリを引き続き O(1) に抑えたまま、サイクルが始まるノードも見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
nextをたどってノード 0 から進みます。サイクルのないリストは-1で停止しますが、サイクルのあるリストは停止しません。ぐるぐる回っていることに気づくには、何を覚えておく必要がありますか？訪問済みのノードに印を付ける方法は機能しますが、すべてのノードについてメモリが必要です。代わりに、2つのポインターを異なる速度でリストに沿って進めます。リストにループがある場合、それらの間の距離はどうなるでしょうか？
1ラウンドごとに
slowを1つ、fastを2つ進めます。fastまたはnext[fast]が-1なら、サイクルはありません。2つのポインターが同じノードに到達した場合、サイクルがあります。
解説
サイクルのないリストは-1にn個のリンクをたどるうちに到達しますが、サイクルのあるリストはいつまでも終わらないため、終端を待つことはできません。たどっている経路が周回していることを検知する方法が必要です。訪れたノードをすべて記憶する方法では、O(n)のメモリを使います。Floydの高速ポインタと低速ポインタなら、整数2つで検知できます。ループ内では、2倍の速さで進むポインタが低速ポインタに必ず追いつくからです。
訪問したノードに印を付ける
考え方
ノード 0 からたどり始め、各ノードを離れるときに印を付けます。すでに印が付いているノードに到達したら、たどり道がそこに戻ってきたことになり、そこから先は永遠に繰り返されます。これがサイクルです。例 1 では、0、1、2、3 に印を付けます。ノード 3 からのリンクは、すでに印が付いているノード 1 につながっています。
ノードには 0 から n-1 まで番号が付いているので、長さ n のブール配列を訪問済みノードの集合として使えます。オブジェクトで構成された連結リストの場合は、代わりにノードへの参照をハッシュセットに格納します。考え方は同じです。
各ノードに印を付けるのは最大 1 回で、たどる処理は最初の再訪時または -1 に到達した時点で停止するため、ステップ数は最大 n です。印を付ける処理に必要な時間は O(n)、メモリは O(n) です。
アルゴリズム
- 長さ
nのブール配列visitedを作成し、すべての要素をfalseにします。 node = 0を設定します。nodeが-1でない間、visited[node]がすでにtrueならtrueを返します。- そうでなければ、
visited[node]を設定し、next[node]に進みます。 - たどっている途中で
-1に達したら、falseを返します。
def hasCycle(next):
visited = [False] * len(next)
node = 0
while node != -1:
if visited[node]:
return True # back at a node already on the path
visited[node] = True
node = next[node]
return False速いポインターと遅いポインター（Floydの循環検出）
考え方
2つのポインターを先頭に置きます。slowは1ラウンドに1つのリンクを進み、fastは2つ進みます。リストの末尾に達すると、fastが先に-1に到達し、falseを返します。サイクルがある場合、fastが先にその中に入り、slowも到着するまで回り続けます。
両方がサイクル内に入ると、各ラウンドでfastはslowに対してちょうど1ノード分進みます。fastがslowに到達するまでの距離はラウンドごとに1ずつ減るため、やがてゼロになり、ポインターは同じノードを指します。1回に1ノードずつ進むので、fastがslowを飛び越えることはありません。
例1では、1ラウンド後、slowはノード1に、fastはノード2にいます。2ラウンド後、slowはノード2にいて、fastは3、1と進んでいます。3ラウンド後には両方ともノード3にいるので、答えはtrueです。
slowがサイクルに入るまでに必要なラウンド数は最大でn回で、サイクル内に入ると1周する前に2つのポインターが出会うため、時間計算量はO(n)です。必要なメモリは2つのノード番号だけです。
アルゴリズム
slow = 0とfast = 0を設定します。fastが-1ではなく、next[fast]も-1ではない間、slowを1つ先のリンクへ、fastを2つ先のリンクへ進めます。- 移動するたびに、同じノード上にあれば
trueを返します。 - ループが停止したとき、
fastは末尾に到達しています。falseを返します。
def hasCycle(next):
slow = 0
fast = 0
# fast needs two links to move; if either is missing, the list ends.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
return True
return False
落とし穴と境界ケース
ここでのバグは、リストの末尾と、どのノードを数えるかに関するものです。
- 両方を確認せずに
fastを2つ先のリンクまで進めること。next[next[fast]]を読み取る前に、fastとnext[fast]がどちらも実在するノードでなければなりません。そうでないとnext[-1]を読み取ることになり、ほとんどの言語ではクラッシュし、Pythonでは何事もなく最後の要素が返されます。 - ポインターを進める前に比較すること。どちらもノード0から始まるため、ループの先頭で確認すると、どのリストでもサイクルがあると報告されます。
- たどる経路ではなく、配列全体を見ること。
[-1, 2, 1]ではノード1と2がループを形成しますが、先頭ノードはすぐに終端するため、答えはfalseです。next内で値が繰り返されているかどうかを確認するのも誤りです。[4, 4, 4, 4, -1]では複数のノードがノード4につながっていますが、サイクルはありません。 - サイクルは必ず先頭ノードに戻ると思い込むこと。
[1, 2, 3, 4, 4]では最後のノードが自分自身につながり、[0]では先頭ノードが自分自身につながります。
よくある質問4
Floydの循環検出はどのように機能しますか？
2つのポインターが先頭から開始します。一方は1ステップにつき1つのリンクを進み、もう一方は2つ進みます。サイクルがなければ、速い方が末尾に到達します。サイクルがある場合、両方ともその中に入り、速い方は1ステップにつき1ノードずつ差を詰め、同じノードで出会います。
連結リストのサイクルの時間計算量と空間計算量はどのくらいですか？
どちらの方法も、各ノードを一定回数だけ通過するため、時間計算量は O(n) です。訪問済みノードを記録するには、追加で O(n) のメモリが必要です。Floydの速いポインターと遅いポインターでは、2つのノード番号分の O(1) のメモリが必要です。
なぜ速いポインターは遅いポインターを飛び越せないのでしょうか？
サイクル内では、各ラウンドでfastは2つのノードを進み、slowは1つ進むため、fastがslowに到達するまでに進む必要のある距離は、ちょうど1ずつ減少します。ラウンドごとに1ずつ減少する距離は3、2、1、0となり、0を通り越すことはないため、2つのポインターは同じノードで出会います。
手順を数えることでサイクルを検出できますか？
この配列形式では、はい。循環のないリストは n 個のリンク以内に -1 に到達するため、終端に到達せずに n 個のリンクをたどったことは、O(1) のメモリで循環があることを証明します。この方法にはノード数が必要ですが、ポインターで構成されたリストからはその数がわかりません。また、先にノード数を数えようとしても、循環がある場合は処理が終わりません。Floyd の方法では数を数える必要はありません。
Python
def hasCycle(next):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
next = [1, 2, 3, 1]
期待値
true