Leetcode 2 Add Two Numbers

发表于 |

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

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

题意分析：
用两个非空链表表示两个数字，然后将这两个数字作加法，最后所求结果也以链表形式表示

思路分析：
这道题十分友好，因为我们作加法需要从个位开始计算，这道题直接将个位就放在链表的头部，方便我们计算。

唯一要注意的点就是考虑进位的问题，我们使用一个flag来表示是否要进位，初始为0

有个小技巧，当l1和l2长度不相等时，我们可以默认长度不够的那一段全都是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 68ms, beats 95.45%
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        # 表示进位
        flag = 0
        # ret存储返回结果
        ret = head = ListNode(0)
        # 以长的为标准
        while l1 or l2:
            # 长度不够的按0算
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            val = (val1 + val2 + flag) % 10
            head.next = ListNode(val)
            head = head.next
            flag = (val1 + val2 + flag) // 10
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        # 考虑l1 = [5], l2=[5]这种情况，循环结束后还有进位没有处理，所以单独处理
        if flag == 1: head.next = ListNode(1)
        return ret.next

(trick: 我们也可以分别把每个链表中的数字真正读出来，然后做加法，最后再转成成链表的形式)