【Python】リンクリスト内のサイクル（循環）を検出するプログラムの書き方

リンクリスト（連結リスト）の中にサイクル（循環参照）が存在するかどうかを検出したい場面は少なくありません。本記事では、リンクリストへ要素を追加するメソッドや指定位置のノードを取得するメソッドを定義したうえで、フロイドの循環検出法（Floyd's Cycle Detection Algorithm）とも呼ばれる「slow / fast ポインタ」のテクニックを使って、サイクルの有無を効率的に判定するPythonプログラムを紹介します。

このアルゴリズムでは、1つずつ進む「遅いポインタ（slow）」と2つずつ進む「速いポインタ（fast）」を同時に走らせます。リンクリスト内にサイクルが存在すれば、速いポインタが一周して遅いポインタに追いつき、両者が同じノードで一致する瞬間が必ず訪れます。逆にサイクルがなければ、速いポインタが先にリストの終端（None）に到達します。

以下に具体的な実装例を示します。

サンプルコード

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


class LinkedList_structure:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_vals(self, data):
        # リンクリストの末尾に新しい要素を追加する
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

    def get_node_val(self, index):
        # 指定されたインデックスのノードを取得する
        curr = self.head
        for i in range(index):
            curr = curr.next
            if curr is None:
                return None
        return curr


def check_cycle(my_list):
    # slowは1つずつ、fastは2つずつ進める
    slow_val = my_list.head
    fast_val = my_list.head
    while fast_val is not None and fast_val.next is not None:
        slow_val = slow_val.next
        fast_val = fast_val.next.next
        if slow_val == fast_val:
            return True
    return False


my_linked_list = LinkedList_structure()
my_list = input('リンクリストに追加する要素をスペース区切りで入力してください: ').split()

for elem in my_list:
    my_linked_list.add_vals(int(elem))

my_len = len(my_list)
if my_len != 0:
    vals = '0-' + str(my_len - 1)
    last_ptr = input('末尾ノードが指すノードのインデックス [' + vals + '] を入力してください'
                     '（何も入力しない場合はNoneを指します）: ').strip()
    if last_ptr == '':
        last_ptr = None
    else:
        last_ptr = my_linked_list.get_node_val(int(last_ptr))
        my_linked_list.last_node.next = last_ptr

if check_cycle(my_linked_list):
    print('このリンクリストにはサイクルが存在します')
else:
    print('このリンクリストにはサイクルが存在しません')

実行結果

サイクルがない場合

リンクリストに追加する要素をスペース区切りで入力してください: 56 78 90 12 4
末尾ノードが指すノードのインデックス [0-4] を入力してください（何も入力しない場合はNoneを指します）:
このリンクリストにはサイクルが存在しません

サイクルがある場合

末尾ノードのnextを途中のノード（例：インデックス1）に向けると、リストがループ状につながり、サイクルが発生します。

リンクリストに追加する要素をスペース区切りで入力してください: 56 78 90 12 4
末尾ノードが指すノードのインデックス [0-4] を入力してください（何も入力しない場合はNoneを指します）: 1
このリンクリストにはサイクルが存在します

コードの解説

• Nodeクラスの作成： 各ノードが保持するデータ（data）と、次のノードへの参照（next）を属性として持つ「Node」クラスを定義します。

• LinkedList_structureクラスの作成： リンクリスト本体を管理するためのクラスです。コンストラクタ（__init__）では、先頭ノードを表す「head」と末尾ノードを表す「last_node」を「None」で初期化します。

• add_valsメソッド： リンクリストの末尾に新しい値を追加するためのメソッドです。まだ要素が1つもない場合はheadに設定し、それ以外の場合はlast_nodeのnextに新しいノードをつなげます。

• get_node_valメソッド： 指定したインデックス位置にあるノードを取得するメソッドです。範囲外のインデックスが指定された場合はNoneを返します。

• check_cycle関数： slowポインタを1ステップずつ、fastポインタを2ステップずつ進めながら、両者が同じノードで一致するかどうかを調べます。一致すればサイクルが存在すると判断できます。

• 戻り値： サイクルが見つかった場合はTrue、見つからないままfastポインタが終端に達した場合はFalseを返します。

• プログラムの実行： LinkedList_structureのインスタンスを作成し、ユーザーからの入力値をリンクリストに追加します。必要に応じて末尾ノードのnextを任意のノードに向けることで、意図的にサイクルを作ることも可能です。

• 結果の出力： 最後にcheck_cycle関数を呼び出し、その判定結果をコンソールに表示します。

なお、この手法の計算量はO(n)、必要な追加メモリはO(1)です。訪問済みノードをハッシュセットなどで記録する方法と比べてメモリ効率に優れている点が、フロイドの循環検出法の大きなメリットといえます。