目錄
- 題目及分析
- 解法一: 迭代法
- 解法二: 遞歸法
- 解法三:反轉鏈表法
題目及分析
(力扣序號2:兩數相加)
給你兩個非空的鏈表,表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的,并且每個節點只能存儲 一位 數字。
請你將兩個數相加,并以相同形式返回一個表示和的鏈表。
你可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
示例 1:
輸入:l1 = [2,4,3], l2 = [5,6,4]
輸出:[7,0,8]
解釋:342 + 465 = 807.
示例 2:
輸入:l1 = [0], l2 = [0]
輸出:[0]
示例 3:
輸入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出:[8,9,9,9,0,0,0,1]
提示:
每個鏈表中的節點數在范圍 [1, 100] 內
0 <= Node.val <= 9
題目數據保證列表表示的數字不含前導零
解法一: 迭代法
基本思路:
- 創建一個啞節點作為結果鏈表的頭節點。
- 初始化一個變量
carry
為0,用于存儲進位值。 - 使用一個循環遍歷兩個鏈表,直到兩個鏈表都為空且沒有進位:
- 將兩個鏈表對應位置的值和
carry
相加。 - 計算新的節點值和新的進位值。
- 創建一個新節點,存儲計算出的節點值,并將其連接到結果鏈表的末尾。
- 移動鏈表指針到下一個節點。
- 將兩個鏈表對應位置的值和
- 返回結果鏈表的頭節點。
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 解法一:迭代法
def add_two_numbers_iterative(l1: ListNode, l2: ListNode) -> ListNode:dummy_head = ListNode(0)current = dummy_headcarry = 0while l1 or l2 or carry:val1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10current.next = ListNode(total % 10)current = current.nextif l1:l1 = l1.nextif l2:l2 = l2.nextreturn dummy_head.next
解法二: 遞歸法
基本思路:
- 如果兩個鏈表和進位都為空,返回None。
- 計算當前節點的和及新的進位值。
- 創建一個新節點,存儲計算出的節點值。
- 遞歸處理下一個位置的值和進位。
- 返回新節點。
# 解法二:遞歸法
def add_two_numbers_recursive(l1: ListNode, l2: ListNode, carry=0) -> ListNode:if not l1 and not l2 and not carry:return Noneval1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10result = ListNode(total % 10)l1_next = l1.next if l1 else Nonel2_next = l2.next if l2 else Noneresult.next = add_two_numbers_recursive(l1_next, l2_next, carry)return result
解法三:反轉鏈表法
基本思路:
- 由于鏈表存儲的是逆序的數字,可以將兩個鏈表反轉,使得數字變為正序。
- 反轉后按照正常的加法計算,最后再將結果鏈表反轉,得到最終結果。
- 這種方法需要注意鏈表的反轉和恢復。
# 解法三:反轉鏈表法
def reverse_list(head: ListNode) -> ListNode:prev = Nonecurrent = headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prevdef add_two_numbers_reverse(l1: ListNode, l2: ListNode) -> ListNode:l1 = reverse_list(l1)l2 = reverse_list(l2)dummy_head = ListNode(0)current = dummy_headcarry = 0while l1 or l2 or carry:val1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10current.next = ListNode(total % 10)current = current.nextif l1:l1 = l1.nextif l2:l2 = l2.nextreturn reverse_list(dummy_head.next)