🤖
141. Linked List Cycle
リンクリストの先頭ノード head が与えられたとき、そのリンクリストにサイクル（循環）があるかどうかを判断してください。
リンクリストにサイクルがあるとは、次のポインタを連続してたどることで、再び同じノードに戻ることができる場合を指します。内部的に、pos は尾ノード（最後のノード）の next ポインタが接続されているノードのインデックスを表すために使用されます。なお、pos はパラメータとして渡されません。
リンクリストにサイクルがある場合は true を返し、ない場合は false を返してください。
入出力例
例1:
入力: head = [3,2,0,-4], pos = 1
出力: true
説明: リンクリストにはサイクルがあり、尾が1番目のノード（0インデックス）に接続されています。
例2:
入力: head = [1,2], pos = 0
出力: true
説明: リンクリストにはサイクルがあり、尾が0番目のノードに接続されています。
例3:
入力: head = [1], pos = -1
出力: false
説明: リンクリストにはサイクルがありません。
制約条件
- リスト中のノード数は
[0, 10^4]の範囲です。 - 各ノードの値は
-10^5 <= Node.val <= 10^5の範囲です。 -
posは-1またはリンクリスト内の有効なインデックスです。
フォローアップ
この問題を O(1) （定数）メモリで解決できますか？
フロイドのサイクル検出アルゴリズム（2ポインタ法：速いポインタと遅いポインタ）
- 速いポインタ（fast） は2ステップずつ進み、遅いポインタ（slow） は1ステップずつ進む。
- サイクルが存在する場合、速いポインタと遅いポインタは必ずどこかで交差します。
- サイクルが存在しない場合、速いポインタが
Noneに到達して終了します。 - このアルゴリズムは、O(1) のメモリを使用し、O(n) の時間計算量で解決できます。
Discussion