python3兩數相加的實現示例
兩數相加
給你兩個 非空 的鏈表,表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的,並且每個節點隻能存儲 一位 數字。
請你將兩個數相加,並以相同形式返回一個表示和的鏈表。
你可以假設除瞭數字 0 之外,這兩個數都不會以 0 開頭。
示例 1:
輸入:l1 = [2,4,3], l2 = [5,6,4]
輸出:[7,0,8]
解釋:342 + 465 = 807.
示例 2:
輸入:l1 = [0], l2 = [0]
輸出:[0]
示例 3:
輸入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出:[8,9,9,9,0,0,0,1]
思路:
1.創建一個新鏈表,新鏈表的頭部先設置為l1頭部和l2頭部之和。
2.遍歷兩個鏈表,隻要有一個還沒有遍歷完就繼續遍歷
3.每次遍歷生成一個當前節點cur的下一個節點,其值為兩鏈表對應節點的和再加上當前節點cur產生的進位
4.更新進位後的當前節點cur的值
5.循環結束後,因為首位可能產生進位,因此如果cur.val是兩位數的話,新增一個節點
6.返回頭節點
由題目註釋可以看出listNode這個類是用來創建鏈表的,默認next=None,val=0.
Definition for singly-linked list.
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: head = ListNode(l1.val+l2.val) current = head while l1.next or l2.next: l1 = l1.next if l1.next else ListNode() l2 = l2.next if l2.next!=None else ListNode() current.next = ListNode(l1.val+l2.val+current.val//10) current.val = current.val%10 current = current.next if current.val >= 10: current.next = ListNode(current.val//10) current.val = current.val%10 return head
改進改進:增加瞭空間復雜度。本以為一方為None後直接把另一個鏈表連上就ok瞭。然後,就打臉瞭。
然後又加瞭while
> [9999] # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: head = ListNode(l1.val+l2.val) current = head while l1.next and l2.next: l1 = l1.next l2 = l2.next current.next = ListNode(l1.val+l2.val+current.val//10) current.val = current.val%10 current = current.next if l1.next == None and l2.next : while l2.next: l2 = l2.next current.next= ListNode(l2.val+current.val//10) current.val = current.val%10 current = current.next current.next = l2.next elif l2.next == None and l1.next: while l1.next: l1 = l1.next current.next= ListNode(l1.val+current.val//10) current.val = current.val%10 current = current.next current.next = l2.next if current.val >= 10: current.next = ListNode(current.val//10) current.val = current.val%10 return head
到此這篇關於python3兩數相加的實現示例的文章就介紹到這瞭,更多相關python3兩數相加內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- None Found