問題
給出兩個 非空 的連結清單用來表示兩個非負的整數。其中,它們各自的位數是按照 逆序 的方式存儲的,并且它們的每個節點隻能存儲 一位 數字。
如果,我們将這兩個數相加起來,則會傳回一個新的連結清單來表示它們的和。
您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4),輸出:7 -> 0 -> 8。
原因:342 + 465 = 807
思路及解答
1. Python實作
# 方法一:類型轉換
# 把連結清單的元素讀到一個清單中,然後将清單轉換為數值類型,再進行相加運算。
# 時間複雜度:O(2m+2n)
# 利用清單進行計算不如用字元串進行計算友善,因為用字元串隻需用int()進行轉換即可,而用清單還要除十、模十進行計算才能得到數值。
# 方法二:類型轉換(Python 的連結清單操作還不是很明白,需要自己單步調試一下)
# 把連結清單的元素讀入到一個字元串中,然後将字元串轉換為數值類型,再進行相加運算。
# 時間複雜度:O(2m+2n)
# 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:
str1, str2 = "", ""
p1, p2 = l1, l2
# 将連結清單元素放到字元串中
while p1 is not None:
str1 = str(p1.val) + str1 # 拼接字元串
p1 = p1.next
while p2 is not None:
str2 = str(p2.val) + str2
p2 = p2.next
# 進行相加運算
result = int(str1) + int(str2)
# 将結果逐位放到連結清單(這之後不太明白)
result = str(result)
l3 = l4 = ListNode(0) # 定義了兩個節點 l3 和 l4,分别初始化為值為零,next 指針為空。這樣寫表示 l3 和 l4 完全一樣,是以下面對 l3 的操作同樣也改變了 l4。
for index in range(len(result)-1, -1, -1): # 從字元串最後一位到第一位進行索引
l3.next = ListNode(int(result[index])) # 本來是不存在l3.next的,這一步相當于定義了l3.next節點,并且進行了指派
l3 = l3.next
return l4.next
# 方法三:逐位相加
# 将連結清單每一位對應相加,若無進位carry=0;若有進位carry=1。位之和是對應兩數之和再加上進位标志位再模十(carry要麼為0,要麼為1);carry為對應兩數之和再加上進位标志位再整除十。
# 時間複雜度:O(max(m, n))
# 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:
result, carry = [], 0 # 進位标志位初始化為0
while(l1 or l2 or carry):
if l1 == None: # 這兩步是防止 l1 或者 l2 為空,則不會再有 next 屬性。
l1 = ListNode(0)
if l2 == None:
l2 = ListNode(0)
# result.append((l1.val + l2.val) % 10 + carry) # 這樣寫不對,因為要加上進位标志位才可以模十。
result.append((l1.val + l2.val + carry) % 10)
carry = (l1.val + l2.val + carry) // 10
l1 = l1.next
l2 = l2.next
# return result # result是個清單,題目要求傳回連結清單,奇怪的是傳回了清單也成功送出了。下面改為連結清單之後,時間複雜度變高。
# 輸對外連結表
tmp = re = ListNode(0)
for i in range(len(result)):
tmp.next = ListNode(result[i])
tmp = tmp.next
return re.next