Pythonで2つの連結リスト（リンクリスト）が同一かどうかを判定するプログラム

プログラミングにおいて、2つの連結リスト（リンクリスト）が同じデータを持っているかどうかを確認したい場面はよくあります。その場合、リンクリストに要素を追加するためのメソッドと、2つのリンクリストの要素が一致しているかどうかを判定するためのメソッドをそれぞれ定義します。

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

サンプルコード

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 check_equality(list_1, list_2):
    curr_1 = list_1.head
    curr_2 = list_2.head
    while (curr_1 and curr_2):
        if curr_1.data != curr_2.data:
            return False
        curr_1 = curr_1.next
        curr_2 = curr_2.next
    if curr_1 is None and curr_2 is None:
        return True
    else:
        return False

my_linked_list_1 = LinkedList_structure()
my_linked_list_2 = LinkedList_structure()

my_list = input('1つ目の連結リストの要素を入力してください: ').split()
for elem in my_list:
    my_linked_list_1.add_vals(int(elem))

my_list = input('2つ目の連結リストの要素を入力してください: ').split()
for elem in my_list:
    my_linked_list_2.add_vals(int(elem))

if check_equality(my_linked_list_1, my_linked_list_2):
    print('2つの連結リストは同じです')
else:
    print('2つの連結リストは同じではありません')

実行結果

1つ目の連結リストの要素を入力してください: 34 56 89 12 45
2つ目の連結リストの要素を入力してください: 57 23 78 0 2
2つの連結リストは同じではありません

コードの解説

• まず、個々のノードを表す「Node」クラスを作成します。各ノードはデータ（data）と次のノードへの参照（next）を持ちます。
• 次に、必要な属性を持つ「LinkedList_structure」クラスを作成します。
• このクラスには __init__ 関数があり、先頭ノードを指す「head」と末尾ノードを指す「last_node」を初期値「None」で初期化します。
• 「add_vals」メソッドを定義し、リンクリストの末尾へ新しい値を追加できるようにします。リストが空の場合はheadに設定し、そうでなければlast_nodeの後ろに新しいノードを連結します。
• さらに、「check_equality」関数を定義し、2つの連結リストの要素が同じかどうかを判定します。
• この関数は、両方のリストを先頭から順に走査しながら各ノードのデータを比較し、一致するかどうかに応じて True または False を返します。片方だけ残りのノードがある場合は False となります。
• 「LinkedList_structure」クラスのインスタンスを2つ生成します。
• ユーザーからの入力を受け取り、それぞれの連結リストに整数として要素を追加します。
• 2つの連結リストを引数として「check_equality」メソッドを呼び出します。
• 判定結果がコンソールに出力されます。

なお、このアルゴリズムの計算量は O(n) です。長いリスト同士を比較する場合でも、先頭から一度だけ走査すればよいため、効率的に動作します。