2024-11-02|閱讀時間 ‧ 約 0 分鐘

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

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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.