DSA Interview Prep · レッスン

Floydのアルゴリズムによる循環検出

Q: 「Floydのアルゴリズムによる循環検出」レッスンは無料ですか？

はい。「Floydのアルゴリズムによる循環検出」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

Q: 「Floydのアルゴリズムによる循環検出」で何を学びますか？

slow-fastポインターで循環を検出し、循環の開始点を見つけ、アルゴリズムの正しさを数学的に証明します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Q: DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

Q: 「Floydのアルゴリズムによる循環検出」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

slow-fastポインターで循環を検出し、循環の開始点を見つけ、アルゴリズムの正しさを数学的に証明します。

「Floydのアルゴリズムによる循環検出」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

連結リストのサイクルとは

連結リストのサイクルとは、あるノードの next ポインタが以前に訪れたノードを指し、無限ループが発生する状態です。このようなリストを while head ループで走査すると、処理が永遠に終わりません。サイクル検出は面接でよく出題される古典的な問題であり、より高度なポインタアルゴリズムの基礎でもあります。

単純な方法では、訪問したすべてのノードを集合に保存し、含まれているかどうかを確認します。これは O(n) 時間、O(n) 空間です。Floyd のアルゴリズムなら、同じ問題を O(n) 時間かつ O(1) 空間 で解決できます。面接官が期待しているのはこちらです。

Floyd のスロー・ファストポインタアルゴリズム

Floyd のサイクル検出（「亀と兎」）では、2つのポインタを使います。slow は一度に1ステップ進み、fast は2ステップ進みます。サイクルがなければ、先に fast が None に到達します。サイクルがある場合は、fast がサイクル内で slow を追い越し、最終的に同じノードで出会います。この出会いによって、サイクルの存在が証明されます。

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

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

スローとファストが必ず出会う理由

直感的には、両方のポインタがサイクルに入ると、ポインタ間の距離は1ステップごとに1ずつ変化します（fast は2、slow は1進むため、1回ごとに差が1縮まります）。やがて差が0になり、同じノードに到達します。より形式的には、サイクルの長さを C とすると、サイクル内の最大の差は C-1 です。差は1ステップごとに1縮まるため、両方がサイクルに入ってから C ステップ以内に出会います。

出会うまでの合計ステップ数は最大でも O(n + C) = O(n) です。これは C <= n だからです。

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

サイクルの入口ノードを見つける

サイクルを検出した後、Floyd のアルゴリズムでは入口ノード（サイクルが始まるノード）も見つけられます。slow と fast がサイクル内で出会ったら、一方のポインタを先頭に戻し、もう一方は出会った位置に置いたままにします。その後、両方を一度に1ステップずつ進めます。すると、サイクルの入口ノードで正確に出会います。これは、先頭から入口までの距離と、出会った位置から入口までの距離が、サイクルの長さを法とすると等しいためです。

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

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

入口ノードの数学的証明

F = 先頭からサイクルの入口までの距離、C = サイクルの長さ、a = 入口からサイクル内の出会った位置までの距離とします。出会ったとき、slow は F + a ステップ進んでおり、fast は F + a + n*C ステップ進んでいます（fast は n 周分多く進んでいます）。fast = 2 * slow なので、2(F+a) = F+a+nC → F = nC - a となります。これは、先頭から入口までの距離と、出会った位置から入口までの距離が、C を法として等しいことを意味します。一方のポインタを先頭に戻して両方を1ステップずつ進めると、入口ノードで合流します。

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

サイクルの長さの測定

Floyd のアルゴリズムのフェーズ1でサイクル内の出会った位置を見つけたら、サイクルの長さを測定できます。一方のポインタをその場に止め、もう一方を再び出会うまで進めます。進んだステップ数がサイクルの長さです。サイクルの長さそのものを求める問題で役立ちます。

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

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

Happy Number（リストを使わないサイクル検出）

Floyd のアルゴリズムは連結リストに限定されません。LeetCode 202 の「Happy Number」では、n をその各桁の2乗和に繰り返し置き換えたとき、最終的に1に到達するかどうかを判定します。1を含まないサイクルに入ると、永遠にループします。これを、各ノードの「next」が次に計算された値を表す仮想的な連結リストの走査としてモデル化し、Floyd のアルゴリズムを適用してサイクルを検出できます。

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

単純な集合ベースの検出と Floyd の比較

集合ベースの方法では、訪問した各ノードを集合に保存し、訪問する前に含まれているかを確認します。これは O(n) 時間、O(n) 空間です。Floyd のアルゴリズムも O(n) 時間ですが、追加のデータ構造を使わないため、空間は O(1) だけです。メモリに制約のある環境（組み込みシステムやオペレーティングシステムのカーネルなど）では、O(1) 空間が保証されることが重要です。面接官は、集合を使った解法を示した後の追加質問として、O(1) 空間での解法を明示的に求めることがあります。

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

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

サイクル検出のエッジケース

処理すべきエッジケースは3つあります。1つ目は、空のリストです。head is None の場合、Floyd のループ条件 fast and fast.next はすぐに終了し、False を返します。2つ目は、サイクルのない1ノードのリストです。fast.next が None なので、ループが終了し、False を返します。3つ目は、サイクルのある1ノードのリストです。ノードの next が自分自身を指します。slow と fast はどちらも先頭から開始し、1ステップ後には fast が head.next.next = head へ進み、slow は head.next = head に位置します。そのため、最初の反復で fast == slow になります。

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

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

連結リストのサイクル II：LeetCode 142

LeetCode 142 の「Linked List Cycle II」では、サイクルが始まるノード（サイクルがなければ None）を求めます。これは Floyd の2フェーズアルゴリズムを直接適用する問題です。面接では、基本的なサイクル検出に続く追加問題として出題されます。解法全体は、フェーズ1でサイクル内の出会った位置を見つけ、フェーズ2で一方のポインタを先頭に戻し、両方を前方へ進めて出会うまで歩かせます。その出会った位置がサイクルの入口です。

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

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

Floyd が集合ベースの方法に勝る理由

どちらの方法も時間計算量は O(n) ですが、実際の定数倍のコストは異なります。集合ベースの方法では、各ノードポインタをハッシュ化し（ハッシュ値を計算し、ハッシュテーブルを検索し、ポインタを保存する）、一方で Floyd はポインタの参照だけを行うため、1ステップあたりのコストがはるかに低くなります。さらに重要なのは、O(1) 空間が保証されるため、Floyd はメモリ不足のリスクなく、任意の長さのリストを処理できることです。

面接でこの空間計算量の利点を自発的に説明すると、単なる Big-O 記法を超えて、アルゴリズム上のトレードオフを深く理解していることを示せます。

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンの振り返り

このレッスンでは、Floyd のスロー・ファストポインタアルゴリズムによって、サイクルを O(n) 時間、O(1) 空間で検出できること、フェーズ2（一方のポインタを先頭に戻し、両方を1ずつ進める）によって正確なサイクルの入口ノードを見つけられること、そして「next」が関数で表される任意の暗黙的な数列に、連結リスト以外でも同じ手法を適用できることを学びました。次は、ソート済みリストのマージ、中央でのリストの分割、末尾から n 番目のノードの探索を扱います。

よくある質問