leetcode with python:2. Add Two Numbers

由于前面几题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 = nextclass 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%)

那我们下题见