🐰

Floyd's Cycle Detection（ウサギとカメのアルゴリズム）を実装して動作イメージをつかむ

に公開
Python
プログラミング
アルゴリズム
LeetCode
tech

はじめに

連結リストのサイクル検出には、Floyd's Cycle Detection（ウサギとカメのアルゴリズム）というアルゴリズムがあります。

連結リストではポインタを順にたどる必要がありますが、このアルゴリズムでは2つのポインタを異なる速度で動かすことでサイクルの有無を判定できます。

本記事では図を使ってアルゴリズムの流れを確認し、Pythonで実装までやってみます。

アルゴリズムの仕組み

2つのポインタを🐢と🐇で表します。
例えばですが、それぞれ次のような進み方をするものとします。

🐢 カメ：1歩ずつ進む
🐇 ウサギ：2歩ずつ進む

ケース1：サイクルなし

🐇 は2歩ずつ進むので、🐢より早く先に進み続け最終的にはnull（終点）にたどり着きます。
🐇 が null に着いたらサイクルなしと判断できます。

ケース2：サイクルあり

ウサギがカメより速く走る（例：🐇は2歩、🐢は1歩ずつ進む）ので、
もし道がサイクルのある輪になっていれば、どこかのステップで🐇は、🐢に同じ場所で追いつくことになります。
たとえば下記のようなイメージです。

サイクルありの例

  • 前提
    • ノード1 ~ 4があり4 → 2の部分でループしてる
    • 🐢：1歩ずつ進む
    • 🐇：2歩ずつ進む
ステップ 🐢の位置 🐇の位置 状況
0 1 1 スタート地点
1 2 3 1周目開始
2 3 2 ウサギが2周目に突入
3 4 4 ノード4で出会った！→ サイクルあり

実装して手元で動かしてみる

プロジェクト構造
root
├─ linked_list.py          # 連結リストの基本操作
├─ cycle_detector.py       # サイクル検出アルゴリズム
├─ cycle_maker.py          # テスト用のサイクル作成
└─ main.py                 # 実行例

linked_list.py

連結リストの基本的なデータ構造と操作を行うスクリプトです。

def create_node(value, next_node=None):
    """
    連結リストのノードを作成
    
    引数:
        value: ノードに格納する値
        next_node: 次のノードへの参照
    
    戻り値:
        ノードを表す辞書
    """
    return {"value": value, "next": next_node}


def build_linked_list(values):
    """
    配列から連結リストを作成
    
    引数:
        values: 値の配列
    
    戻り値:
        連結リストの先頭ノード
    """
    if not values:
        return None
    
    nodes = []
    for value in values:
        new_node = create_node(value)
        nodes.append(new_node)

    # この時点で nodes = [
    #   {"value": 1, "next": None},
    #   {"value": 2, "next": None},
    #   {"value": 3, "next": None}
    # ]

    for i in range(len(nodes) - 1):
        nodes[i]["next"] = nodes[i + 1]

    # この時点で nodes = [
    #   {"value": 1, "next": nodes[1]},  # 1 → 2
    #   {"value": 2, "next": nodes[2]},  # 2 → 3
    #   {"value": 3, "next": None}       # 3 → None
    # ]

    return nodes[0]

例えば、build_linked_list([1, 2, 3])を実行した後のnodes[0]をprintすると、

{'value': 1, 'next': {'value': 2, 'next': {'value': 3, 'next': None}}}

このように、nodes[0]の中に全てのノードが数珠つなぎになって格納されているように見えます。

実際には

  • nodes[0]は1つ目のノードオブジェクト
  • その"next"プロパティにnodes[1]への参照が入っている
  • nodes[1]の"next"にはnodes[2]への参照が入っている
  • このように参照を辿ることで、先頭ノードから全てのノードにアクセス可能

cycle_detector.py

Floyd's Cycle Detection Algorithm（ウサギとカメのアルゴリズム）です。

def detect_cycle(head):
    """
    連結リストのサイクル検出
    
    アルゴリズム:
        - slowポインタ: 1歩ずつ進む
        - fastポインタ: 2歩ずつ進む
        - サイクルがあれば必ず出会う
    
    引数:
        head: 連結リストの先頭ノード
    
    戻り値:
        True: サイクルあり / False: サイクルなし
    """
    if not head:
        return False
    
    slow = head  # 🐢 ノード1（nodes[0]）
    fast = head  # 🐇 ノード1（nodes[0]）
    
    while fast and fast.get("next"):
        # ポインタを進める処理　1周目
        slow = slow["next"] # ノード2
        fast = fast["next"]["next"] # ノード3

        # 同じノードで会った時
        if slow is fast:
            return True # サイクルあり
    
    return False　# fastがNoneに到達 → サイクルなし

cycle_maker.py

テスト用のサイクル作成ツールです。

def create_cycle(head, position):
    """
    連結リストにサイクルを作成
    
    引数:
        head: 連結リストの先頭ノード
        position: サイクルの戻り先の位置（0始まり）
    """

    # head が正常な場合の想定例： head = {"value": 1, "next": None} 
    # position が正常な場合の想定例： position = 1
    if not head or position < 0:
        return

    # ステップ1: 全ノードを配列に格納
    all_nodes = []
    current = head
    while current:
        all_nodes.append(current)
        current = current["next"]
    # この時点で all_nodes = [ノード1, ノード2, ノード3, ノード4]

    # ステップ2: 最後のノードを取得
    last_node = all_nodes[-1]

    # ステップ3: 指定位置が有効なら、サイクルを作成
    if position < len(all_nodes):
        target_node = all_nodes[position]　# target_node = ノード2 (position=1)
        last_node["next"] = target_node　# ノード4 → ノード2 に繋ぐ
        # 結果: 1 → 2 → 3 → 4 → 2 (サイクル完成)

main.py

連結リストのサイクル検出デモ用のスクリプトです。

from linked_list import build_linked_list
from cycle_detector import detect_cycle
from cycle_maker import create_cycle


# ケース1：サイクルあり
list_with_cycle = build_linked_list([1, 2, 3, 4])
# 4 → 2 のループを作成（`position=1` はノード2を指す）
create_cycle(list_with_cycle, position=1)
print("サイクルあり:", detect_cycle(list_with_cycle))
# 出力: サイクルあり: True

# ケース2：サイクルなし
list_without_cycle = build_linked_list([10, 20, 30])
print("サイクルなし:", detect_cycle(list_without_cycle))
# 出力: サイクルなし: False

実行結果

main.pyを実行すると、以下の結果が得られます。

サイクルあり: True
サイクルなし: False
  • ケース1：ノード4がノード2に繋がっているため、サイクルが検出される
  • ケース2：通常の連結リストなので、サイクルなしと判定される

Floyd's Cycle Detectionアルゴリズムでループの有無が検知できていることが確認できます。
コーディング試験でも頻出のアルゴリズムのようなので、覚えておきたいところです。

Discussion