Add Two Numbers

3 Python実装（LeetCode形式）

from __future__ import annotations
from typing import Optional, TYPE_CHECKING

if TYPE_CHECKING:
    class ListNode:
        val: int
        next: Optional[ListNode]
        def __init__(self, val: int = 0, next: Optional[ListNode] = None) -> None: ...
else:
    try:
        from leetcode_structures import ListNode  # type: ignore
    except (ImportError, ModuleNotFoundError):
        class ListNode:
            __slots__ = ("val", "next")
            def __init__(self, val: int = 0, next: Optional[ListNode] = None) -> None:
                self.val = val
                self.next = next


class Solution:
    """
    LeetCode 2: Add Two Numbers

    2つの逆順連結リストで表された非負整数を加算し、
    結果を逆順連結リストで返す。

    時間計算量: O(n) - n = max(len(l1), len(l2))
    空間計算量: O(1) - 出力ノードを除く補助空間
    """

    def addTwoNumbers(
        self,
        l1: Optional[ListNode],
        l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        """
        2つの逆順リストの和を逆順リストで返す。

        Args:
            l1: 第1の数の逆順連結リスト（最下位桁が先頭）
            l2: 第2の数の逆順連結リスト（最下位桁が先頭）

        Returns:
            和を表す逆順連結リスト
        """
        # 番兵ノード: 先頭ノードの特別処理を排除
        dummy: ListNode = ListNode(0)
        tail: ListNode = dummy

        # 走査ポインタと繰り上がり
        p: Optional[ListNode] = l1
        q: Optional[ListNode] = l2
        carry: int = 0

        # いずれかのリストが残るか、繰り上がりが残る限り処理
        while p is not None or q is not None or carry != 0:
            # 現在の桁の値を取得（リストが終了していれば0）
            x: int = p.val if p is not None else 0
            y: int = q.val if q is not None else 0

            # 桁の和 + 繰り上がりを計算
            sum_: int = x + y + carry
            carry = sum_ // 10  # 新しい繰り上がり
            digit: int = sum_ % 10  # 現在の桁の値

            # 結果ノードを生成して末尾に追加
            tail.next = ListNode(digit)
            tail = tail.next

            # ポインタを前進（存在する場合のみ）
            if p is not None:
                p = p.next
            if q is not None:
                q = q.next

        # 番兵の次が実際の結果の先頭
        return dummy.next