由於前面幾題easy覺得難度還可以負荷,因此開始嘗試medium的題目

題目:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

ex:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

給兩個linked list,各別代表一個數字,再以linked list型態回傳兩者相加的值
從範例可以看到linked list型態的值是顛倒的,這其實幫了我很大的忙

我是以直式加法的概念下去實作

# 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]:
        ll=ListNode() #紀錄欲回傳linkedlist的head
        ans=ll
        
        i=0
        while True:
            ll.next=ListNode((l1.val+l2.val+i)%10)
            i=(l1.val+l2.val+i)//10
            l1=l1.next
            l2=l2.next
            ll=ll.next
            
            if l1==None:
                while l2: #(1)
                    ll.next=ListNode((l2.val+i)%10)
                    i=(l2.val+i)//10
                    l2=l2.next
                    ll=ll.next
                break
                
            if l2==None:
                while l1: #(1)
                    ll.next=ListNode((l1.val+i)%10)
                    i=(l1.val+i)//10
                    l1=l1.next
                    ll=ll.next
                break
                
        if i!=0: #(2)
            ll.next=ListNode(i)
            
        return ans.next

以//10求出的i代表了直式加法中的進位,而%10得出留在該位數的值
而與原值顛倒的輸入讓進位更加容易進行
直式加法的觀點有兩部分需要特別注意:
(1)兩linked list不一樣長:
即跑到一個linked list無值時,另一個還有值
正常來說可以將餘值直接延續在欲回傳的linked list上
但要特別注意是否有遺留的i值及其是否會導致進位
(2)突破兩linked list的最高位:
最後相加完記得檢查是否有突破的i值,像999+999=1998兩三位數相加進位到四位數
最後執行時間為59ms(faster than 99.24%)

那我們下題見