🐇
結合リストのサイクル検出：ポインタの速度差を利用しろ【怠けないウサギは初めてだ】

2025/11/21に公開
 目次解いた問題

学び

最初に考えた解法

正解

感想

 解いた問題leetcode 141. Linked List Cycle

「このリストはサイクルしているか？」を調べる問題。
内部的にpolという変数が設定されており、pol=-1ならループ無し、それ以外ならpolはノードのインデックスを指し、最後尾がどこにループしているかを指す。
当然polはプログラム中から参照できないので、ループしているかどうかは回してどうにか判定しなきゃいけないっすよ、判定してみてねって問題。
leetcodeの説明を何回見ても理解できなかったのでAIにめちゃめちゃ聞いて理解できました。

 学びハッシュテーブルはdictだけでなくsetも使えるし何なら便利
内部で速度差のあるポインタを使ってループの有無が確認できる
アルゴリズムの世界のウサギは怠けない

 最初に考えた解法O(1)という条件があったので、前回やったビット演算を使用して重複があったらTrueをreturnして、無いならFalseをreturnというのを考えた。
前回のはこちら↓

https://zenn.dev/zenn_mita/articles/f9811270b871d5
しかし前回と異なって2回出る値を返さなくてはならず、うまくいきそうになかったので断念。
O(1)はいったん考えず、ハッシュマップを使って返すことを考えた。

それが下記。
 first.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        map = {}
        
        while 1:
            if head.next is None:
                return False
            map[head.val] = map.get(head.val, 0) + 1
            if map[head.val] == 2:
                return True
            head = head.next
練習問題では正解になったのでsubmitしたところエラーに。

問題を見てみるとheadの中に同じ数値が入っていて、かつループ無しという問題。
実装したハッシュマップだと「同じ数値が出たときTrue返却」という設計になっているため、ループの有無にかかわらずTrueを返してしまう。
3分考えましたがぐうの音も出なかったのでここでギブアップ。正解を確認しました。

 正解まずハッシュマップを使った場合の正解が下記。
 answer_hashmap.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()         # ここに「通ったノードそのもの」を入れていく

        node = head
        while node is not None:
            if node in visited: # 同じノードに2回目に来た → サイクルあり
                return True
            visited.add(node)   # 初めて見るノードなので記録
            node = node.next    # 次へ進む

        # None に到達した → サイクルなし
        return False
setを使用して、通ったノードインスタンスそのものを格納、重複の有無を見ているようです。

setのいいところはkeyが不要なところ。いちいち+1などして重複を確認する必要がないのがいいですね。
ちなみにsetを使ったハッシュテーブル方式は「ハッシュセット」というそう。

まんまですね。
ただこれだとO(n)なため、O(1)の解法も確認。それが下記。
 answer_best.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 空リスト or 要素1つだけならサイクルは作れない
        if head is None or head.next is None:
            return False

        slow = head
        fast = head

        # fast と fast.next が None でない間だけ進める
        while fast is not None and fast.next is not None:
            slow = slow.next          # 1ステップ
            fast = fast.next.next     # 2ステップ

            # 同じノードを指したらサイクルあり
            if slow is fast:
                return True

        # どこかで None に到達した → サイクルなし
        return False
「Floyd’s Tortoise and Hare Algorithm」という名前のアルゴリズムでウサギと亀。

このアルゴリズムのウサギは怠け者ではなかったようです。
slowを1つずつ、fastを2つずつポインタをずらすことによって、ループがなければfastかそのnextがNoneになるし、ループがあればslowとfastがさすノードが一致する点が必ずできる。
なので回していったら必ずTrueを返せるということになる。

 感想おもしろい。
凡人には0→1ででてこない発想に感じていますが、一度やったアルゴリズムは使えるようになっている感覚があるのでかなり楽しいです。
継続していきます！
目次

解いた問題

学び

最初に考えた解法

正解

感想

Discussion
