Pythonで連結リストとして表された2つの数値を加算する方法

問題概要

空でない連結リストが2つ与えられ、それぞれが非負の整数を表しているものとします。桁は逆順に格納されており、各ノードには1桁の数字のみが含まれています。この2つの数値を足し合わせ、その結果を連結リストとして返すのが課題です。ただし、数値0自体を除き、先頭に余分なゼロ（leading zeros）は含まれないものと仮定します。

例えば、120 + 230 を計算する場合、連結リストは次のように表されます。

[0 → 2 → 1] + [0 → 3 → 2] = [0 → 5 → 3] = 350

解法のアルゴリズム

この問題は、筆算と同じ要領で各桁を順番に足していき、繰り上がり（carry）を管理することで解決できます。手順は以下の通りです。

1. 2つのリスト l1 と l2 を受け取り、head と temp を None で初期化します。
2. 繰り上がり用の変数 c を 0 で初期化します。
3. l1 または l2 のどちらかが空でない限り、以下の処理を繰り返します。
   • l1 が空なら a := 0、そうでなければ a := l1.val とします。
   • l2 が空なら b := 0、そうでなければ b := l2.val とします。
   • n := a + b + c を計算します。
   • n > 9 なら c := 1、そうでなければ c := 0 とします。
   • n mod 10 を値に持つ新しいノードを作成します。
   • head が None の場合は head := node、temp := node とします。
   • そうでなければ head.next := node とし、head := node で head を進めます。
   • l1 が存在すれば次のノードへ、l2 も同様に次のノードへ進めます。
4. ループ終了後も c が 0 でない場合は、値 1 のノードを新しく作成して末尾に接続します（最上位桁への繰り上がり）。
5. temp（結果リストの先頭）を返します。

Pythonでの実装例

以下のコードは、上記のアルゴリズムをPythonで実装したものです。

class ListNode:
    def __init__(self, data, next=None):
        self.val = 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 print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = None
        temp = None
        c = 0
        while l1 or l2:
            if not l1:
                a = 0
            else:
                a = l1.val
            if not l2:
                b = 0
            else:
                b = l2.val
            n = a + b + c
            c = 1 if n > 9 else 0
            node = ListNode(n % 10)
            if not head:
                head = node
                temp = node
            else:
                head.next = node
                head = node
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        if c:
            node = ListNode(1)
            head.next = node
        return temp

ob1 = Solution()
l1 = make_list([0, 2, 1])
l2 = make_list([0, 3, 2])
print_list(ob1.addTwoNumbers(l1, l2))

入力

[0,2,1]
[0,3,2]

出力

[0,5,3]

計算量について

このアルゴリズムでは、2つのリストのうち長い方の長さを n とすると、時間計算量は O(n)、結果リストを格納するため空間計算量も O(n) となります。各ノードを一度だけ走査すればよい構造になっているため、非常に効率的な解法です。