1 題目描述


這題就是兩個鍊錶表示的數相加，這樣就可以實現兩個很大的數相加了，關鍵要能無需考慮數值 int ，float 的限制了。但是如果你把 ListNode 直接串啟程字串並且轉換成數字，這你就大錯特錯了！因為這樣就失去了這題的意義了。

2 解法

2.1 我的解法

我一開始沒意識到，這題的 ListNode 是倒序的，所以我一開始的想法是把兩個 ListNode 轉換成數字，然後相加，再轉換成 ListNode。但是這樣就失去了這題的意義了。因為有一個test case是超級長的[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]直接突破了int的限制。

所以我的解法無法通過這個 test case。建議參考下一個方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        """
        1. 先串起來成字串 [2, 3, 4] => 432, [5, 6, 4] => 465
        2. 字串轉換成數字後相加 int(432) + int(465) = 807
        3. 807 mode 10 一個個串入 7 -> 0 -> 8
        """
        l1_str = ""
        l2_str = ""
        while l1:
            l1_str = str(l1.val) + l1_str
            l1 = l1.next
        while l2:
            l2_str = str(l2.val) + l2_str
            l2 = l2.next

        tot = int(l1_str) + int(l2_str)
        val = tot % 10
        head = ListNode(val)

        current = head
        while current:
            tot = int(tot / 10)
            val = tot % 10
            if tot == 0:
                break
            new_node = ListNode(val)
            current.next = new_node
            current = current.next

        return head

2.2 最佳解法

這題的精髓在於有以下兩個特點：

  1. 從個位數往前一個個相加：為了實現兩個很大的數值相加，不被 int 的限制，我們在相加的時候可以從倒序 listnode 開始相加，也就是 123 + 456 的時候，我們從 3+6 開始。因此 123 需要先變成 321，456 需要先變成 654。這樣才可以從個位數（3與6）開始相加。
  2. 處理商數：再來第二點是，我們要處理商數，也就是進位的問題。因此我們需要一個變數 carry 來處理進位的問題。如果個位數相加的時候，發現有進位的需求，我們就把進位的數字加到下一個數字相加的時候。
  3. dummy_head：如果我們要處理第一個 ListNode 就是兩個 ListNode 的第一個值相加的話，這可能會導致整個程式碼很攏長，要先檢查是否None，然後取出第二個數值，再相加。確保好第一個ListNode才可以進入while迴圈，但是檢查的事項又要重新做第二次，因此還不如直接先造出一個假的 ListNode，然後最後再返回 dummy_head.next 就好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def addTwoNumbers2(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy_head = ListNode(0) # 原來還可以隨便塞一個，最後 return dummy_head.next 就好 （記得把 dummy_head.next 清空）
    cur = dummy_head
    carry = 0
    while l1 is not None or l2 is not None or carry != 0:
        digit1 = l1.val if l1 else 0
        digit2 = l2.val if l2 else 0

        sum = digit1 + digit2 + carry
        digit = sum % 10
        carry = sum // 10

        cur.next = ListNode(digit)
        cur = cur.next

        l1 = l1.next if l1 is not None else None
        l2 = l2.next if l2 is not None else None

    result = dummy_head.next
    dummy_head.next = None
    return result

3 總結

這題我也沒有在時間內解出來，直接去看答案了，雖然我的想法跟答案有點像，但是我還是傻傻的先把ListNode轉換成數字的字串，再用這個字串從第一個字串開始處理，太蠢了！！！可以直接拿ListNode開始處理，人家都幫你倒敘排好了…簡單來說，根本不用這樣做：

1
2
3
4
5
6
7
8
9
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    l1_str = ""
    l2_str = ""
    while l1:
        l1_str = str(l1.val) + l1_str
        l1 = l1.next
    while l2:
        l2_str = str(l2.val) + l2_str
        l2 = l2.next