在這篇文章中，我們將深入探討 LeetCode 題目「2. Add Two Numbers」的解法，並提供兩種不同的解題方法來處理此問題。這道題目考察對鏈結串列 (Linked List) 操作和進位處理的掌握。
題目描述：
給定兩個非空的鏈結串列，表示兩個非負整數。數字以逆序存儲，每個節點只包含一位數字。將這兩個數相加，並以相同的鏈結串列形式返回結果。範例：
Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807.
解題思路
要解決這道題目，我們需要逐位相加兩個鏈結串列的數字，並處理進位情況。遍歷兩個鏈結串列，對應節點的值相加，記錄進位 (carry)，直到鏈結串列的所有節點和進位都處理完畢。
方法：迭代解法
思路：
- 初始化一個帶有假頭節點（dummy node）的結果鏈結串列。
- 從兩個鏈結串列的頭部開始逐位相加，如果某一個鏈結串列比另一個短，則視為其值為 0。
- 當兩個數字相加大於或等於 10 時，記錄進位，並在下一位的相加中考慮這個進位。
- 當所有節點處理完後，如果還有進位，需在結果鏈結串列的末尾新增一個節點來存放進位值。
迭代解法程式碼：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(0)
current = dummy_head
carry = 0
# 當 l1, l2 其中之一還沒走完，或有進位時，繼續處理
while l1 or l2 or carry:
l1_val = l1.val if l1 else 0
l2_val = l2.val if l2 else 0
total = l1_val + l2_val + carry
# 計算當前位數的值和進位
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
# 移動到下一個節點
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy_head.next
解法解析：
- 時間複雜度：O(n)，其中 n 是較長鏈結串列的長度。因為我們只需遍歷兩個鏈結串列一次。
- 空間複雜度：O(n)，由於需要儲存結果鏈結串列的所有節點。
結語
「Add Two Numbers」這道題目主要考察我們對鏈結串列的操作和進位處理的理解。迭代解法相對直觀，適合初學者掌握，而遞歸解法則更具挑戰性，適合遞歸思維熟練者。你可以根據個人習慣選擇最適合的解法。
這兩種方法都能有效解決這道問題，無論是面試還是日常編程，都有很高的實用性。
