兩數相加
- 題目
- 解答思路
- python 代碼
題目位址
題目
給出兩個 非空 的連結清單用來表示兩個非負的整數。其中,它們各自的位數是按照 逆序 的方式存儲的,并且它們的每個節點隻能存儲 一位 數字。
如果,我們将這兩個數相加起來,則會傳回一個新的連結清單來表示它們的和。
您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出:7 -> 0 -> 8
原因:342 + 465 = 807
解答思路
- 兩個連結清單從頭開始周遊,沒一位相加
- 如果 和 大于 10, 那麼需要 進一位
- 注意邊界, 兩個連結清單邊界 和 進位
python 代碼
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = ListNode(0)
node_ = head
carry = 0
while l1 or l2 or carry:
sum_ = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry = sum_ // 10
node_.next = ListNode(sum_ % 10)
node_ = node_.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return head.next