LeetCode如何實現兩個數字相加

LeetCode如何實現兩個數字相加

在LeetCode上，實現兩個數字相加是一個經典的算法問題。這個問題通常以鏈表的形式出現，要求我們將兩個表示非負整數的鏈表相加，并返回一個新的鏈表來表示它們的和。本文將詳細介紹如何解決這個問題。

問題描述

給定兩個非空鏈表，表示兩個非負整數。每個鏈表中的節點表示一個數字位，且鏈表中的數字是逆序存儲的。例如，鏈表 2 -> 4 -> 3 表示數字 342。我們的任務是將這兩個鏈表表示的數字相加，并返回一個新的鏈表來表示它們的和。

解題思路

1. 初始化變量：我們需要一個變量 carry 來存儲進位值，初始值為 0。同時，我們需要一個虛擬頭節點 dummy 來簡化鏈表的操作，以及一個指針 current 來跟蹤當前節點。

2. 遍歷鏈表：我們同時遍歷兩個鏈表，直到兩個鏈表都到達末尾。在每次迭代中，我們計算當前節點的值以及進位值的和，然后更新 carry 和當前節點的值。

3. 處理進位：如果遍歷結束后 carry 仍然大于 0，我們需要在結果鏈表的末尾添加一個新節點來存儲這個進位值。

4. 返回結果：最后，我們返回虛擬頭節點的下一個節點，即結果鏈表的頭節點。

代碼實現

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next
        
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    
    return dummy.next

復雜度分析

• 時間復雜度：O(max(n, m))，其中 n 和 m 分別是兩個鏈表的長度。我們需要遍歷兩個鏈表中的每一個節點。
• 空間復雜度：O(max(n, m))，結果鏈表的長度最多為 max(n, m) + 1。

總結

通過上述方法，我們可以有效地解決LeetCode上的兩個數字相加問題。關鍵在于正確處理進位和鏈表的遍歷。希望本文能幫助你更好地理解這個問題，并在實際編程中應用這一算法。