題目出處
難度
medium
個人範例程式碼
基本版本
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = head = ListNode(0)
carry = 0
while(l1 and l2):
this_val = l1.val + l2.val + carry
carry = this_val // 10
head.next = ListNode(this_val % 10)
l1 = l1.next
l2 = l2.next
head = head.next
else:
while(l1):
this_val = l1.val + carry
carry = this_val // 10
head.next = ListNode(this_val % 10)
l1 = l1.next
head = head.next
while(l2):
this_val = l2.val + carry
carry = this_val // 10
head.next = ListNode(this_val % 10)
l2 = l2.next
head = head.next
if carry:
head.next = ListNode(carry)
return dummy.next
算法說明
- - 當 l1, l2 還有值時，為第一階段
- 其中一個沒有值時，用 while 去將剩下的 l1 或 l2 掃完
- 最後判定有沒有剩餘的 carry
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為空的情況，這裡我是直接回傳 None。
Boundary conditions
注意 LinkList 的結束條件：
- 結束的 None 也算是一個節點。 會被 if node 判為 False。
與之相對應的是使用 node.next 來判斷，
可是因為 node.next 依然可以走到 None 的 Node，因此容易因此而判錯。
優化版本
優化，將 l1, l2, carry 有無剩餘的內容一起看，一路處理到沒剩餘內容為止。
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = head = ListNode(0)
carry = 0
while(l1 or l2 or carry): # something still exist
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
head.next = ListNode(carry % 10)
head = head.next
carry = carry // 10
else:
return dummy.next