LeetCode題目記錄---兩數相加（1）

LeetCode題目記錄

• 題庫-力扣
• • 2.兩數相加

題庫-力扣

2.兩數相加

https://leetcode-cn.com/problems/add-two-numbers/

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

如果，我們将這兩個數相加起來，則會傳回一個新的連結清單來表示它們的和。

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

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

1. 思路：

   題中涉及的運算是數值相加，資料輸入和輸出都是以連結清單形式存在的，每個節點存放的是一位數字，數字的位數是按照逆序的方式存儲的，是以可以考慮以計算加法豎式的思路來解決本題。

   先建構一個連結清單用于存放輸出值，目前節點存放的是個位數的值，後續節點存放的是更高位數的值。先将輸入值的目前節點進行相加，和的個位數存放在輸對外連結表的目前節點，十位數用于計算輸對外連結表下一個節點的值；接下來就按照同樣的思路計算下一個節點，在求節點和的時候要加上上一節點和的十位數；如此疊代直至兩個輸傳入連結表的節點均窮盡，當僅有一個連結清單窮盡時可以給該連結清單補0值。當兩個數最高位數的和是大于9時需要再增加一個數字的位數用于存放和的十位數。即當兩個連結清單最後一次的和為兩位數時，将其十位數存放在輸對外連結表的下一個節點中。

2. 代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        re = ListNode(0)
        r=re
        carry=0
        while(l1 or l2):
            x= l1.val if l1 else 0
            y= l2.val if l2 else 0
            s=carry+x+y
            carry=s//10
            r.next=ListNode(s%10)
            r=r.next
            if(l1!=None):l1=l1.next
            if(l2!=None):l2=l2.next
        if(carry>0):
            r.next=ListNode(1)
        return re.next   #re的結構和r第一個節點的結構是一樣的