何がしたい? 🤔

連結リストの循環を検出
循環が始まるノードを探す

基本的なアイデア💡

このアルゴリズムでは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/