[LeetCode解題攻略] 2. Add Two Numbers

在這篇文章中，我們將深入探討 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)，直到鏈結串列的所有節點和進位都處理完畢。

方法：迭代解法

思路：

1. 初始化一個帶有假頭節點（dummy node）的結果鏈結串列。
2. 從兩個鏈結串列的頭部開始逐位相加，如果某一個鏈結串列比另一個短，則視為其值為 0。
3. 當兩個數字相加大於或等於 10 時，記錄進位，並在下一位的相加中考慮這個進位。
4. 當所有節點處理完後，如果還有進位，需在結果鏈結串列的末尾新增一個節點來存放進位值。

迭代解法程式碼：

# 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」這道題目主要考察我們對鏈結串列的操作和進位處理的理解。迭代解法相對直觀，適合初學者掌握，而遞歸解法則更具挑戰性，適合遞歸思維熟練者。你可以根據個人習慣選擇最適合的解法。

這兩種方法都能有效解決這道問題，無論是面試還是日常編程，都有很高的實用性。