Pythonでフロイドの循環検出法(Floyd's cycle-finding algorithm)

# 何がしたい? 🤔
- 連結リストの循環を検出
- 循環が始まるノードを探す

# 基本的なアイデア💡

このアルゴリズムでは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が同じノードで重なった場合，循環が存在する．

## 循環の開始ノードの探索🏁
1. slowとfastが同じノードを指したら，**slowのみ**headに戻し，fastはそのままにする．
2. slowとfastを両方とも**1ステップずつ**進める.
3. slowとfastが再び同じノードを指したとき，そのノードが循環の開始ノードである．

## 実際にやってみる
1~5の連結リストで3~5が循環している場合
```text title:連結リストの例
1 -> 2 -> 3 -> 4 -> 5
          |_________|
```
この連結リストはNode3が循環の開始地点になっています．
### 循環の存在確認
1.初期状態
- slowとfastはどちらもheadを指す

```text
slow: 1
fast: 1
```

2.1回目の移動
- slowは1ステップ，fastは2ステップ進む

```text
slow: 2
fast: 3
```

3.2回目の移動
- slowは1ステップ，fastは2ステップ進む

```text
slow: 3
fast: 5
```

4.3回目の移動
- slowは1ステップ，fastは2ステップ進む

```text
slow: 4
fast: 4
```
fastは3 -> (4) -> 5 -> (3) -> 4 という移動をしています．()内は2ステップで飛ばしています．


**結論: ここでslowとfastは同じノード(4)を指しているので，サイクルが存在していることがわかった✅**

### 循環の始点ノードの特定
5.slowをheadに戻す
- 循環検出後，slowをhead(リストの先頭)に戻す．

```text
slow: 1
fast: 4
```

6.slowとfastを1ステップ進める(両者が再び出会うまで続ける👩‍❤️‍👨)

```text
slow: 2
fast: 5
```
```text
slow: 3
fast: 3
```
**結論: slowとfastがNode3で出会ったのでこのノードが循環の始点ノードであるとわかった✅**

以下フロー↓
```text
1 -> 2 -> 3 -> 4 -> 5
          ^          |
          |----------|

初期:
slow: 1
fast: 1

1回目:
slow: 2
fast: 3

2回目:
slow: 3
fast: 5

3回目:
slow: 4
fast: 4 (一致 → 循環検出)
```

```text
slow を head に戻す:
slow: 1
fast: 4

1回目:
slow: 2
fast: 5

2回目:
slow: 3
fast: 3 (一致 → サイクル開始地点)
```

# なぜこれが成り立つのか
1. 循環内での動き
fast pointerはslow pointerの2倍の速さで進むため，もし循環が存在すれば，fastはslowに1周して追いつきます．
- fastはslowに対して1ステップずつ差を縮める
- 差分が0になる地点でslowとfastは同じノードを指す

2. 循環の開始ノード
slowをheadに戻し，slowとfastを同じ速さで進めると，再び出会う場所が循環の開始地点になります．

# 計算量 🧮
各pointer が連結リストを1度通るだけで済むため，計算量はO(n)
*nはノード数

# コード例 Python🐍
```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/