Pythonで2つの連結リストの対応する位置の要素を加算する方法

2つの連結リスト（リンクリスト）の対応する位置にある要素同士を加算したい場合、「連結リストへ要素を追加するメソッド」「連結リストの内容を表示するメソッド」「対応する位置の要素を加算する関数」の3つを定義します。その後、連結リストのインスタンスを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 print_it(self):
        curr = self.head
        while curr is not None:
            print(curr.data)
            curr = curr.next

def add_linked_list(my_list_1, my_list_2):
    sum_list = LinkedList_structure()
    curr_1 = my_list_1.head
    curr_2 = my_list_2.head
    while (curr_1 and curr_2):
        sum_val = curr_1.data + curr_2.data
        sum_list.add_vals(sum_val)
        curr_1 = curr_1.next
        curr_2 = curr_2.next
    if curr_1 is None:
        while curr_2:
            sum_list.add_vals(curr_2.data)
            curr_2 = curr_2.next
    else:
        while curr_1:
            sum_list.add_vals(curr_1.data)
            curr_1 = curr_1.next
    return sum_list

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))

sum_list = add_linked_list(my_list_1, my_list_2)

print('The sum of elements in the linked list is ')
sum_list.print_it()

実行結果

Enter the elements of the first linked list : 56 34 78 99 54 11
Enter the elements of the second linked list : 23 56 99 0 122 344
The sum of elements in the linked list is 
79
90
177
99
176
355

処理の解説

• まず、ノードを表す「Node」クラスを作成します。各ノードはデータ（data）と次のノードへの参照（next）を持ちます。

• 続いて、必要な属性を備えた「LinkedList_structure」クラスを作成します。

• このクラスには「__init__」関数があり、先頭ノードを表す「head」と末尾ノードを表す「last_node」を「None」で初期化します。

• 「add_vals」メソッドを定義し、連結リストの末尾に新しい値を追加できるようにします。

• 「print_it」メソッドを定義し、連結リスト内のすべての値を順番に表示できるようにします。

• さらに「add_linked_list」関数を定義し、2つの連結リストの対応する位置の要素を加算して新しい連結リストを生成します。

• 「LinkedList_structure」クラスのインスタンスを2つ作成し、ユーザーからの入力をもとに両方の連結リストへ要素を追加します。

• これらの連結リストを引数として「add_linked_list」関数を呼び出します。

• 最後に、加算結果の連結リストの内容がコンソールに出力されます。

ポイント

この実装では、2つの連結リストの長さが異なる場合にも対応しています。片方のリストの走査が終わった後、残った側の要素をそのまま結果のリストに追加する処理が組み込まれているため、長さの違うリストでも正しく動作します。また、各リストを一度だけ走査するため、計算量はO(n)となり、効率的な処理が可能です。