Open2

Fast and Slow Pointers パターン

tshtsh

Fast and Slow Pointers パターン

1. Fast and Slow Pointers パターンの基本アイデア

Fast and Slow Pointers パターン（別名 Floyd’s Tortoise and Hare アルゴリズム）は、主に 単方向につながったデータ構造（例: リンクリスト、配列など）を扱う際に利用される手法です。2 つのポインタを異なる速度（通常は slow が 1 ステップ、fast が 2 ステップ）で移動させることで、以下のような問題を効率よく解決できます。

  1. サイクル（ループ）の検出
    リンクリストや配列上でループが存在するとき、slow と fast はいずれ同じノードを指すタイミングが生まれます。

  2. サイクルの長さ・開始地点の特定
    上記のサイクル検出後、追加の手続きでサイクルの始点や長さを求められます。

  3. リストの中央要素の検出
    fast が末端に到達する時点で slow は中央を指すため、リストの中央要素を簡単に見つけられます。

  4. パリンドローム判定
    fast/slow で中央を見つけた後、後半リストを反転して前半と比較する、といった手順の補助に使われます。

2. どのような問題に適用できるか

  1. リンクリストのサイクル検出

    • 例: Linked List Cycle (LeetCode 141)
    • 単一リンクリストが与えられ、サイクルが存在するかどうかを判定する。

  2. リンクリストのサイクル開始地点の特定

    • 例: Linked List Cycle II (LeetCode 142)
    • サイクルがある場合、その開始ノード（ループの入り口）を特定する。

  3. リンクリストの中央要素の特定

    • 例: Middle of the Linked List (LeetCode 876)
    • Fast and Slow を使うことでリストを一度の走査で中央を指せる。

  4. パリンドローム判定

    • 例: Palindrome Linked List (LeetCode 234)
    • Fast/Slow でリストの中央を見つけ、後半部を反転 → 前半部と比較、の流れでパリンドロームかどうかを判断。

  5. 配列を用いたサイクル検出

    • 例: Find the Duplicate Number (LeetCode 287)
    • 配列の値を “次のインデックス” とみなして移動すると、重複する値があるときサイクルが形成される。Floyd’s Tortoise and Hare で検出可能。
tshtsh

3. Python のサンプルコード

3.1 リンクリストのサイクル検出

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next            # 1 ステップ進む
        fast = fast.next.next       # 2 ステップ進む
        if slow == fast:
            return True             # サイクルを検出
    return False                    # サイクルなし

3.2 リンクリストのサイクル開始地点の特定

def detectCycle(head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # サイクル検出後、サイクル開始ノードを探す
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

3.3 リンクリストの中央要素を見つける

def middleNode(head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next       # 1 ステップ進む
        fast = fast.next.next  # 2 ステップ進む
    return slow                # 中央ノード

3.4 配列内サイクル（重複数）の検出例

def findDuplicate(nums: list[int]) -> int:
    # fast and slow の初期化
    slow, fast = nums[0], nums[0]

    # サイクルが生じるまで動かす
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # サイクル開始位置（= 重複している値）を探す
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow