LeetCode-2 两数相加

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目： 两数相加

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

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

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

示例：

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

思路

这题涉及数据结构和链表，这在Python中比较少，参考了官方解题思路才大概明白。

首先需要理解ListNode这个class。

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
	def __init__(self, x):
         self.val = x
         self.next = None

每个ListNode()都有两个属性，一个是本身的值(val)，另一个则是指向另一个ListNode()对象。比如示例中的输出：7 -> 0 -> 8。其实是三个ListNode()对象，产生的过程如下：

1
2
3
4
5
6
7
8
tmp = ListNode(0)
res = tmp
tmp = ListNode(7)
tmp = tmp.next
tmp.next = ListNode(0)
tmp = tmp.next
tmp.next = ListNode(8)
return res.next

对ListNode这样的链表有了理解之后，解题就比较方便了：

  • 先初始化一个tmp = ListNode(0) 的临时变量，并将res.next指向tmp，并初始化一个进位临时变量carry=0
  • 遍历l1,l2直到都为None:
    • 如果l1为None，则x值为0，否则x值为l1.val
    • 如果l2为None，则y值为0，否则y值为l2.val
    • x,y相加并加上上一轮相加的进位carry得到tmpSum，该轮tmp的值为和的tmpSum的个位(tmpSum%10)，carry更新为tmpSum的十位(tmpSum//10)
    • 将tmp在指向自己的下一个tmp.next
  • 遍历结束后检查是否还有进位carry，有的话则tmp的下一位为ListNode(1)
  • 返回结果：res.next

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        tmp = ListNode(0)
        res = tmp
        carry=0
        while l1 or l2:
            if l1:
                x = l1.val
            else:
                x = 0
            if l2:
                y = l2.val
            else:
                y = 0
            tmpSum = carry + x + y
            carry = tmpSum // 10
            tmp.next = ListNode(tmpSum % 10)
            tmp = tmp.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry > 0:
            tmp.next=ListNode(1)
        return res.next

优化方法

上面方法中需要新建一个临时变量来存放l1,l2相加的结果，由于是相加，我们考虑开始就将结果指向l1，在l1的基础上进行计算，思路如下：

  • 设置结果res=l1,初始化一个进位临时变量carry=0
  • 第一阶段l1,l2都有值的时候
    • l1.val,l2.val相加并加上上一轮相加的进位carry得到tmpSum，该轮l1.val的值为更新为tmpSum的个位(tmpSum%10)，carry更新为tmpSum的十位(tmpSum//10)
    • 设定一个临时变量prev指向l1
    • l1,l2均指向自己的下一个l1.next,l2.next
  • 第一阶段结束时，说明l1,l2有一个已经结束了。这时候把l1设定为还未结束的序列（l1 = l1 or l2），并将临时变量prev.next指向新的l1(为了保证序列的连续性，如果前面没有设置的prev临时变量，那么返回结果就中断了)
  • 第二阶段遍历新的l1：
    • l1.val加上上一轮的进位carry得到tmpSum，该轮l1.val的值为更新为tmpSum的个位(tmpSum%10)，carry更新为tmpSum的十位(tmpSum//10)
    • 设定一个临时变量prev指向l1
    • l1指向自己的下一个l1.next
  • 第二阶段结束后，检查是否还有进位carry，有的话则tmp的下一位为ListNode(1)
  • 返回结果：res

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        res = l1
        carry = 0
        while l1 and l2:
            tmpSum = l1.val + l2.val + carry
            carry = tmpSum // 10
            l1.val = tmpSum  % 10
            prev = l1
            l1 = l1.next
            l2 = l2.next
        l1 = l1 or l2
        prev.next = l1
        while l1:
            tmpSum = l1.val + carry
            carry = tmpSum // 10
            l1.val = tmpSum  % 10
            prev = l1
            l1 = l1.next
        if carry > 0:
            prev.next = ListNode(1)
        return res

这道题对Python好像不是很友好，经常会出现超时的情况，如果大家有更好的方法，欢迎一起探讨。