Pythonで連結リストとして表された2つの数値の和を求めるプログラム

この記事では、単方向連結リスト（Singly Linked List）で表された2つの数値を加算し、その結果を新しい連結リストとして返す方法を解説します。

ここでのポイントは、各リストが「最下位桁から順に」数値を格納しているという点です。例えば、リスト [5, 6, 4] は数値「465」を表し、リスト [2, 4, 8] は数値「842」を表します。これらを足すと 465 + 842 = 1307 となるため、出力は [7, 0, 3, 1] になります。

アルゴリズムの考え方

筆算と同じ要領で、各桁を順番に足し合わせながら繰り上がり（carry）を管理します。具体的な手順は以下の通りです。

• 繰り上がりを保持する変数 carry を 0 で初期化します。
• 結果リストの先頭となるダミーノード res（値は 0）を作成し、作業用ポインタ curr を res に設定します。
• L1 または L2 のどちらかに要素が残っている間、あるいは carry が 0 でない限り、以下を繰り返します。
  • L1 の現在の値を l0_val とする（L1 が空なら 0）
  • L2 の現在の値を l1_val とする（L2 が空なら 0）
  • sum_ = l0_val + l1_val を計算
  • (sum_ + carry) を 10 で割った商を新しい carry に、余りを add_val に設定
  • add_val を値とする新ノードを curr.next に接続し、curr を一つ進める
  • L1 と L2 をそれぞれ次のノードへ進める（空なら None）
• ループ終了後、curr.next を None にしてリストを閉じます。
• res.next（ダミーノードの次）を結果として返します。

実装例

それでは、実際の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 solve(self, L1, L2):
        carry = 0
        res = ListNode(0)
        curr = res

        while L1 or L2 or carry:
            l0_val = L1.val if L1 else 0
            l1_val = L2.val if L2 else 0
            sum_ = l0_val + l1_val
            carry, add_val = divmod(sum_ + carry, 10)

            curr.next = ListNode(add_val)
            curr = curr.next

            L1 = L1.next if L1 else None
            L2 = L2.next if L2 else None

        curr.next = None
        return res.next

ob = Solution()
L1 = make_list([5, 6, 4])
L2 = make_list([2, 4, 8])
print_list(ob.solve(L1, L2))

入力

[5,6,4], [2,4,8]

出力

[7, 0, 3, 1]

コードのポイント

• divmod関数の活用： Pythonの divmod(a, b) は商と余りを同時に返すため、繰り上がりの計算が1行で簡潔に書けます。
• ダミーノード： 値 0 のダミーノード res を使うことで、結果リストの先頭処理を特別扱いせずに済み、最後に res.next を返すだけで済みます。
• 桁数が異なる場合にも対応： ループ条件に「L1 or L2 or carry」を採用しているため、片方のリストが短い場合や、最終的な繰り上がりが発生する場合でも正しく動作します。

このアルゴリズムの計算量は、リストの長さを n とした場合に O(n)、必要な追加メモリも結果リスト分のみなので O(n) となります。LeetCodeの「Add Two Numbers」（問題2）などでもおなじみの定番テクニックですので、ぜひマスターしておきましょう。