LeetCode_2_中等_两数相加

---

1. 题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2->4->3], l2 = [5->6->4]
输出：[7->0->8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9->9->9->9->9->9->9], l2 = [9->9->9->9]
输出：[8->9->9->9->0->0->0->1]

---

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 节点处的值的取值范围 0 <= $Node.val$<= 9
• 题目数据保证列表表示的数字不含前导零

2. 思路及代码实现（Python）

题解来源：力扣官方题解

2.1 模拟迭代

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 $n1,n2$，进位值为$\text{carry}$，则它们的和为 $n1+n2+\text{carry}$；其中，答案链表处相应位置的数字为 $(n1+n2+\text{carry})\mathrm{mod}10$，而新的进位值为$?\frac{n1+n2+\text{carry}}{10}?$。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 000 。此外，如果链表遍历结束后，有 $\text{carry}>0$，还需要在答案链表的后面附加一个节点，节点的值为 $\text{carry}$。

需要遍历的次数为两个链表中的较长值，时间复杂度为 $O(max(m,n))$，$m,n$分别为两个链表的长度，而空间复杂度为 $O(1)$，不随着链表长度而增加内存占用。

from typing import Optional

class ListNode:
    def __init__(self, value=0, next=None):
        self.val = value
        self.next = next
        
def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=" ")
        current = current.next

在下面的代码中，创建了一个 cur = dummy = ListNode() 对象，其中 cur 用来不断迭代指向链表的下一个节点，而 dummy 作为哨兵节点，仅标记着最一开始的 ListNode() 对象，因此最后返回的 dummy.next 是结果链表的头节点。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        carry = 0                           # 初始进位为0
        while l1 or l2 or carry:            # 只要链表不空，就继续迭代
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            cur.next = ListNode(carry % 10) # 指向下一个节点
            carry //= 10                    # 更新进位
            cur = cur.next                  # 将指针移到下一个节点
            if l1: l1 = l1.next             # l1 不空则移到下一个节点，为空则在上面会取0
            if l2: l2 = l2.next
        return dummy.next                   # 哨兵节点

示例：

node4 = ListNode(4)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)

node44 = ListNode(7)
node33 = ListNode(3, node44)
node22 = ListNode(2, node33)
node11 = ListNode(2, node22)

res = Solution().addTwoNumbers(node1, node11)
print(print_linked_list(res))

3 4 6 1 1 None

执行用时：52 ms
消耗内存：17.11 MB

2.2 递归

如上述的迭代，我们很容易发现，从两个链表的头节点出发，按位计算操作都是类似的，都是进位加上 $n1+n2$，与10的余数作为相加后的结果，与10的商（地板除法）作为新的进位 $carry$，这可以理解为一个递归问题。

有个注意的点是，在递归时为了简化代码，需基于较长的链表进行递归，但不需要把链表的数都取出来，只需要在递归过程中，当某一链表的下一节点为空时（链表的节点取完了），即为较短链表，交换两个链表的标签即可。

递归的最底部是当两个链表都为空时，此时如果$carry$ 如果不为空，则创建一个值为 $carry$ 的节点，反之，则为 None，时间复杂度为 $O(max(m,n))$，取决于较长链表的长度，而由于递归需要存储栈，空间复杂度也为 $O(max(m,n))$，栈深也取决于较长的链表长度。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:                   # 递归边界：l1 和 l2 都是空节点
            return ListNode(carry) if carry else None   # 如果进位了，就额外创建一个节点
        if l1 is None:  
            l1, l2 = l2, l1
        carry += l1.val + (l2.val if l2 else 0)
        l1.val = carry % 10
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)
        return l1

执行用时：52 ms
消耗内存：16.93 MB

参考题解：灵茶山艾府