何がしたい? 🤔
- 連結リストの循環を検出
- 循環が始まるノードを探す
基本的なアイデア💡
このアルゴリズムでは2つのポインタを使います．
- slow pointer : 1度に1ステップ進む ▶️
- fast pointer : 1度に2ステップ進む ▶️▶️
連結リストを探索する際に，以下の現象を利用します．
- 循環が存在しない場合
fast pointerがリストの末端に到達する． - 循環が存在する場合
循環内をpointerがぐるぐる回って，いつかslow pointerとfast pointerの位置が重なる
アルゴリズムのステップ
サイクルの検出🔁
1. pointer の初期化
slow, fastを連結リストのheadに設定する．(index番号0)
2. pointerを進める
slowを1ステップ, fastを2ステップ進める. (繰り返し)
3. 終了条件
- fast pointerがNoneまたは，fast.nextがNoneに到達した場合，循環が存在しない．
- slow pointerとfast pointerが同じノードで重なった場合，循環が存在する．
循環の開始ノードの探索🏁
- slowとfastが同じノードを指したら，slowのみheadに戻し，fastはそのままにする．
- slowとfastを両方とも1ステップずつ進める.
- slowとfastが再び同じノードを指したとき，そのノードが循環の開始ノードである．
実際にやってみる
1~5の連結リストで3~5が循環している場合
連結リストの例
1 -> 2 -> 3 -> 4 -> 5
|_________|
この連結リストはNode3が循環の開始地点になっています．
循環の存在確認
1.初期状態
- slowとfastはどちらもheadを指す
slow: 1
fast: 1
2.1回目の移動
- slowは1ステップ，fastは2ステップ進む
slow: 2
fast: 3
3.2回目の移動
- slowは1ステップ，fastは2ステップ進む
slow: 3
fast: 5
4.3回目の移動
- slowは1ステップ，fastは2ステップ進む
slow: 4
fast: 4
fastは3 -> (4) -> 5 -> (3) -> 4 という移動をしています．()内は2ステップで飛ばしています．
結論: ここでslowとfastは同じノード(4)を指しているので，サイクルが存在していることがわかった✅
循環の始点ノードの特定
5.slowをheadに戻す
- 循環検出後，slowをhead(リストの先頭)に戻す．
slow: 1
fast: 4
6.slowとfastを1ステップ進める(両者が再び出会うまで続ける👩❤️👨)
slow: 2
fast: 5
slow: 3
fast: 3
結論: slowとfastがNode3で出会ったのでこのノードが循環の始点ノードであるとわかった✅
以下フロー↓
1 -> 2 -> 3 -> 4 -> 5
^ |
|----------|
初期:
slow: 1
fast: 1
1回目:
slow: 2
fast: 3
2回目:
slow: 3
fast: 5
3回目:
slow: 4
fast: 4 (一致 → 循環検出)
slow を head に戻す:
slow: 1
fast: 4
1回目:
slow: 2
fast: 5
2回目:
slow: 3
fast: 3 (一致 → サイクル開始地点)
なぜこれが成り立つのか
- 循環内での動き
fast pointerはslow pointerの2倍の速さで進むため，もし循環が存在すれば，fastはslowに1周して追いつきます．
- fastはslowに対して1ステップずつ差を縮める
- 差分が0になる地点でslowとfastは同じノードを指す
- 循環の開始ノード
slowをheadに戻し，slowとfastを同じ速さで進めると，再び出会う場所が循環の開始地点になります．
計算量 🧮
各pointer が連結リストを1度通るだけで済むため，計算量はO(n)
*nはノード数
コード例 Python🐍
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Step 1: Detect cycle
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Cycle detected
if slow == fast:
# Step 2: Find start of the cycle
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # Start of the cycle
return None # No cycle
# テストコード
def create_cycle_list(values, pos):
"""
サイクルを持つリンクリストを作成する関数
:param values: リストのノードの値（リスト形式）
:param pos: サイクル開始ノードのインデックス (-1 の場合はサイクルなし)
:return: リンクリストのヘッドノード
"""
if not values:
return None
head = ListNode(values[0])
current = head
nodes = [head] # ノードを保存するリスト
for value in values[1:]:
new_node = ListNode(value)
current.next = new_node
current = new_node
nodes.append(new_node)
# サイクルの作成
if pos != -1:
current.next = nodes[pos]
return head
# サンプルリストとサイクル位置を設定
values = [3, 2, 0, -4] # リストノードの値
cycle_pos = 1 # サイクルの開始位置 (0-indexed, -1はサイクルなし)
# サイクルのあるリストを作成
cycle_list = create_cycle_list(values, cycle_pos)
# Solutionクラスを使用してサイクルを検出
solution = Solution()
start_node = solution.detectCycle(cycle_list)
# 結果を出力
if start_node:
print(f"Cycle starts at node with value: {start_node.val}")
else:
print("No cycle detected.")
実行結果
(base) xxx@xxxs-MacBook-Air CodeCamp % python3 -u "/xxx/floyd.py"
Cycle starts at node with value: 2
サイクルが2で始まることがわかる．
参考
https://leetcode.com/problems/linked-list-cycle/description/
https://www.geeksforgeeks.org/floyds-cycle-finding-algorithm/