#2 Add Two Numbers——Top 100 Liked Questions

╰+攻爆jí腚メ 2022-02-12 12:13 105阅读 0赞

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

> """
> 
> 第一次：代码太啰嗦！主要思想是，设置进位标志tmp，遍历两个列表对应位置的值，将对应位置的两个值与进位值相加，result中保留个位值，tmp中保留进位值。分四种情况：l1和l2的位数相同时依次相加；l1的位数大于l2位数时，将l1多余位append到result中，l2位数大于l1位数，将l2多余位append到result中；最后将tmp值append到result中
> 
> """
> 
> \# Definition for singly-linked list.  
> \# class ListNode(object):  
> \#     def \_\_init\_\_(self, x):  
> \#         self.val = x  
> \#         self.next = None
> 
> class Solution(object):  
>     def addTwoNumbers(self, l1, l2):  
>         """  
>         :type l1: ListNode  
>         :type l2: ListNode  
>         :rtype: ListNode  
>         """  
>         tmp = 0  
>         result = \[\]  
>         while l1 != None and l2 != None:  
>             add = l1.val + l2.val + tmp  
>             if add >= 10:  
>                 result.append(add % 10)  
>                 tmp = add // 10  
>             else:  
>                 result.append(add)  
>                 tmp = 0  
>             l1 = l1.next  
>             l2 = l2.next  
>         while l1 != None and l2 == None:  
>             add = l1.val + tmp  
>             if add >= 10:  
>                 result.append(add % 10)  
>                 tmp = add // 10  
>             else:  
>                 result.append(add)  
>                 tmp = 0  
>             l1 = l1.next  
>         while l2 != None and l1 == None:  
>             add = l2.val + tmp  
>             if add >= 10:  
>                 result.append(add % 10)  
>                 tmp = add // 10  
>             else:  
>                 result.append(add)  
>                 tmp = 0  
>             l2 = l2.next  
>         if l1 == None and l2 == None and tmp > 0:  
>             result.append(tmp)
> 
>         head = ListNode(0)  
>         probe = head  
>         for r in result:  
>             probe.next = ListNode(r)  
>             probe = probe.next
> 
>         return head.next
> 
> """
> 
> Runtime: 64 ms, faster than 91.78% of Python online submissions for Add Two Numbers.
> 
> Memory Usage: 11.7 MB, less than 5.16% of Python online submissions for Add Two Numbers.
> 
> """

> """
> 
> 第二次：将上述代码进行更简洁化处理，包括：①上述四种情况可以简化成一个while语句；②if-else语句可以在一行中实现；③新链表的建立可以在程序中实现；④原来分add大于等于10和小于10两种情况，其实根本不用分，此处可合并if-else语句
> 
> """
> 
> \# Definition for singly-linked list.  
> \# class ListNode(object):  
> \#     def \_\_init\_\_(self, x):  
> \#         self.val = x  
> \#         self.next = None
> 
> class Solution(object):  
>     def addTwoNumbers(self, l1, l2):  
>         """  
>         :type l1: ListNode  
>         :type l2: ListNode  
>         :rtype: ListNode  
>         """  
>         tmp = 0  
>         head = ListNode(0)  
>         probe = head  
>         while l1 or l2:  
>             x = l1.val if l1 else 0  
>             y = l2.val if l2 else 0  
>             add = x + y + tmp  
>             probe.next = ListNode(add % 10)  
>             tmp = add // 10  
>             l1 = l1.next if l1 else 0  
>             l2 = l2.next if l2 else 0  
>             probe = probe.next
> 
>         probe.next = ListNode(tmp) if tmp else None
> 
>         return head.next
> 
>  """
> 
> Runtime: 60 ms, faster than 99.41% of Python online submissions for Add Two Numbers.
> 
> Memory Usage: 11.8 MB, less than 5.16% of Python online submissions for Add Two Numbers.
> 
> """