LeetCode(#2) 两数相加-题解笔记 (Python)

2. 两数相加

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

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

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

示例：

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

方法一：

一个偷懒的做法：

首先遍历链表得到两个数字，num1 和 num2，相加得到数字 num 。然后根据相加之后的数字构建链表：

# 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: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            res = l1 if not l2 else l1
            return res
        num1 = 0
        num2 = 0
        h1 = l1
        h2 = l2
        step = 0
        while h1:
            num1 += h1.val * (10**step)
            h1 = h1.next
            step += 1
        step = 0
        while h2:
            num2 += h2.val * (10**step)
            h2 = h2.next
            step += 1
        num = num1 + num2
        head = ListNode()
        node = head
        for x in str(num)[::-1]:
            node.next = ListNode(int(x))
            node = node.next
        return head.next

方法二：

考虑到数字相加会产生进位，用 incr 来储存进位的信息：incr = (node1.val + node2.val + incr) // 10，用 val = (node1.val + node2.val + incr)%10 储存节点值。

在这里可以用递归的思路来解题，定义一个辅助函数：计算 val 和 incr，然后构建 ListNode, 把 incr信息传递给下一个 ListNode

# 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: ListNode, l2: ListNode) -> ListNode:
        def recur(l1, l2, incr):
            if not l1 and not l2 and not incr: return None
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            s = val1 + val2 + incr
            val = s % 10
            incr = s // 10
            node = ListNode(val)
            next1 = l1.next if l1 else None
            next2 = l2.next if l2 else None
            node.next = recur(next1, next2, incr)
            return node
        return recur(l1, l2, 0)