2つの連結リストから最初に共通する要素を見つけるPythonプログラム

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 first_common_val(list_1, list_2):
    curr_1 = list_1.head
    while curr_1:
        data = curr_1.data
        curr_2 = list_2.head
        while curr_2:
            if data == curr_2.data:
                return data
            curr_2 = curr_2.next
        curr_1 = curr_1.next
    return None

my_list_1 = LinkedList_structure()
my_list_2 = LinkedList_structure()

my_list = input('Enter the elements of the first linked list : ').split()
for elem in my_list:
    my_list_1.add_vals(int(elem))

my_list = input('Enter the elements of the second linked list : ').split()
for elem in my_list:
    my_list_2.add_vals(int(elem))

common_vals = first_common_val(my_list_1, my_list_2)

if common_vals:
    print('The element that is present first in the first linked list and is common to both is {}.'.format(common_vals))
else:
    print('The two lists have no common elements')

出力結果

Enter the elements of the first linked list : 45 67 89 123 45
Enter the elements of the second linked list : 34 56 78 99 0 11
The two lists have no common elements

共通要素が存在する場合は、次のように最初に一致した値が出力されます。

Enter the elements of the first linked list : 45 67 89 123 45
Enter the elements of the second linked list : 34 67 78 99 0 11
The element that is present first in the first linked list and is common to both is 67.

プログラムの解説

• まず、各ノードを表す「Node」クラスを作成します。

• 次に、必要な属性を持つ「LinkedList_structure」クラスを作成します。

• このクラスには、先頭要素（head）と末尾要素（last_node）をNoneで初期化するための__init__関数が含まれています。

• 値を連結リストの末尾に追加するための「add_vals」メソッドを定義します。

• さらに、2つの連結リスト内で最初に見つかる共通の値を検索する「first_common_val」メソッドを定義します。

• 「LinkedList_structure」クラスのインスタンスを2つ生成します。

• ユーザーからの入力を受け取り、空白区切りで分割した整数値をそれぞれの連結リストに追加します。

• これらの連結リストに対して「first_common_val」メソッドを呼び出し、戻り値を判定します。

• 共通要素が存在すればその値を、存在しなければ「共通要素なし」のメッセージをコンソールに出力します。

なお、このアルゴリズムは二重ループを使用しているため、計算量はO(m × n)となります。リストの長さがmとnの場合、最悪時にはすべての組み合わせを比較することになります。大量のデータを扱う場合は、片方のリストの値をセット（set）に格納しておき、もう片方のリストを走査しながらO(1)で存在確認を行う方法に置き換えることで、計算量をO(m + n)まで改善できます。