Pythonで連結リストのサイクル（循環）を検出する方法

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

連結リスト（Linked List）の中にサイクル（循環）が存在するかどうかを判定する問題を考えてみましょう。

この問題では、サイクルの有無を表現するために整数値のポインタ pos を使用します。pos は、リストの末尾ノードが接続されている位置を示します。つまり、pos = -1 の場合はサイクルが存在しないことを意味します。

例えば、連結リストが [5, 3, 2, 0, -4, 7] で pos = 1 の場合、末尾ノード（7）が2番目のノード（3）に接続されているため、サイクルが存在することになります。

解法のアプローチ：ハッシュセットを使う

最もシンプルな方法は、ハッシュセット（set）を利用して、すでに訪問したノードを記録しておくことです。同じノードを2回訪れた時点で、サイクルが存在すると判断できます。

アルゴリズムの手順

• ハッシュセット H を1つ用意します。
• head が null でない限り、以下を繰り返します。
  • head がすでに H に存在する場合は True を返します（サイクルあり）。
  • 存在しない場合は head を H に追加します。
  • head を次のノードに進めます。
• ループが終了したら False を返します（サイクルなし）。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

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

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def get_node(head, pos):
    if pos != -1:
        p = 0
        ptr = head
        while p < pos:
            ptr = ptr.next
            p += 1
        return ptr

class Solution(object):
    def hasCycle(self, head):
        hashS = set()
        while head:
            if head in hashS:
                return True
            hashS.add(head)
            head = head.next
        return False

head = make_list([5, 3, 2, 0, -4, 7])
last_node = get_node(head, 5)
pos = 1
last_node.next = get_node(head, pos)

ob1 = Solution()
print(ob1.hasCycle(head))

入力例

List = [5, 3, 2, 0, -4, 7]
Pos = 1

出力結果

True

計算量と補足

このハッシュセットを使った手法は、時間計算量 O(n)、空間計算量も O(n) となります。すべてのノードを最大1回ずつ訪問し、各ノードをセットに保存するためです。

なお、メモリ使用量を抑えたい場合は、フロイドの循環検出法（Floyd's Cycle Detection / うさぎとかめ法）と呼ばれる、速いポインタと遅いポインタの2つを使う手法もあります。こちらは空間計算量 O(1) でサイクルを検出できるため、面接などでもよく話題に上がる定番のアルゴリズムです。