方法一：遞歸

寫法一：創建新節點

算法思路解析

該實現采用 遞歸方式 逐位處理兩個鏈表，并考慮進位 carry：

? 步驟拆解

1. 遞歸終止條件：當 l1, l2 都為空且沒有進位（carry == 0），說明加法結束，返回 None。

2. 當前位求和：s = carry + l1.val (如果有) + l2.val (如果有)

3. 計算當前節點的值與進位：當前節點值為 s % 10，進位為 s // 10

4. 遞歸構造下一節點：遞歸調用 addTwoNumbers(l1.next, l2.next, carry) 處理下一位

5. 創建當前節點并連接：使用 ListNode(s % 10, next_node) 構造當前節點并返回

class Solution:# l1 和 l2 為當前遍歷的節點，carry 為進位def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:if l1 is None and l2 is None and carry == 0:  # 遞歸邊界return Nones = carryif l1:s += l1.val  # 累加進位與節點值l1 = l1.nextif l2:s += l2.vall2 = l2.next# s 除以 10 的余數為當前節點值，商為進位return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))

時間與空間復雜度分析

時間復雜度：O(max(m, n))

• 每次遞歸處理一個節點，最多遞歸 max(m, n) 層（m 和 n 為兩個鏈表的長度）。

空間復雜度：

類型	復雜度	說明
遞歸棧空間	O(max(m, n))	每層遞歸入棧一次
結果鏈表空間	O(max(m, n) + 1)	存儲最終和（可能有一個額外的進位位）

?? 注意：這是遞歸寫法，存在函數棧空間占用，若鏈表極長（如上千位），可能導致棧溢出風險（可改為迭代方式避免）。