LeetCode精選100題（2）——兩數相加

目錄

• • 前言
  • 題目
  • 解題方法

前言

  LeetCode精選100題系列第二題，反思解題中的彎路，解析最佳答案思路。

題目

兩數相加

  給你兩個 非空 的連結清單，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，并且每個節點隻能存儲 一位 數字。

  請你将兩個數相加，并以相同形式傳回一個表示和的連結清單。

  你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例：

輸入：l1 = [2,4,3], l2 = [5,6,4]

輸出：[7,0,8]

解釋：342 + 465 = 807.

解題方法

  同步周遊兩個連結清單，将對應位置數值相加，注意進位。周遊的終止條件對代碼簡潔性影響大。如果選擇周遊最短連結清單，代碼複雜。我們選擇周遊最長連結清單。也就是說最長連結清單結束時，周遊才終止。在周遊期間，短的連結清單會提前結束，這時我們使用0來代替其值即可。

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    carry = 0
    head = h = ListNode(0)
    while l1 or l2 or carry:
        v1, v2 = 0, 0
        if l1:
            v1, l1 = l1.val, l1.next
        if l2:
            v2, l2 = l2.val, l2.next
        n = (v1 + v2 + carry) % 10
        carry = (v1 + v2 + carry) // 10
        h.next = ListNode(n)
        h = h.next
    return head.next
           

  下面是選擇周遊最短連結清單。

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    carry = 0
    h1, h2 = l1, l2
    head = h = ListNode(0)
    while l1 and l2:
        n = (l1.val + l2.val + carry) % 10
        carry = (l1.val + l2.val + carry) // 10
        h.next = ListNode(n)
        h = h.next
        l1 = l1.next
        l2 = l2.next
    
    while l1:
        n = (l1.val + carry) % 10
        carry = (l1.val + carry) // 10
        h.next = ListNode(n)
        h = h.next
        l1 = l1.next
    
    while l2:
        n = (l2.val + carry) % 10
        carry = (l2.val + carry) // 10
        h.next = ListNode(n)
        h = h.next
        l2 = l2.next
    
    if carry:
        h.next = ListNode(carry)
    return head.next