題目出處

2. Add Two Numbers

難度

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

算法說明

1. 當 l1, l2 還有值時，為第一階段
2. 其中一個沒有值時，用 while 去將剩下的 l1 或 l2 掃完
3. 最後判定有沒有剩餘的 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

Reference

• Is this Algorithm optimal or what?