难度: 中等
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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运行时间: 52 ms
内存: 16.9 MB
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
carry = 0
while l1 or l2 or carry == 1:
num = carry
carry = 0
if l1:
num += l1.val
l1 = l1.next
if l2:
num += l2.val
l2 = l2.next
if num >= 10:
num -= 10
carry = 1
p.next = ListNode(num)
p = p.next
return dummy.next
该题解的思路是使用链表的遍历实现两数相加。具体做法是：初始化一个虚拟头节点dummy，同时初始化一个指针p指向dummy，再初始化一个变量carry表示进位。然后同时遍历两个链表l1和l2，每次取出两个链表对应位置的数字相加再加上进位，如果相加结果大于等于10则将进位carry置为1，否则置为0。然后将相加结果的个位数作为新节点的值创建新节点，并将指针p后移。当两个链表都遍历完成后，如果进位carry等于1，还需要再创建一个值为1的新节点。最后返回dummy的下一个节点即为相加的结果。
时间复杂度: O(max(m,n))
空间复杂度: O(max(m,n))
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode() # 初始化虚拟头节点
p = dummy # 初始化指针p指向虚拟头节点
carry = 0 # 初始化进位为0
while l1 or l2 or carry == 1: # 当l1,l2,carry至少有一个非空时循环
num = carry # 当前位的和初始化为进位的值
carry = 0 # 进位重置为0
if l1: # 如果l1非空
num += l1.val # 当前位的和加上l1的当前位
l1 = l1.next # l1后移
if l2: # 如果l2非空
num += l2.val # 当前位的和加上l2的当前位
l2 = l2.next # l2后移
if num >= 10: # 如果当前位的和大于等于10
num -= 10 # 取个位数作为新节点的值
carry = 1 # 进位置为1
p.next = ListNode(num) # 创建新节点
p = p.next # 指针p后移
return dummy.next # 返回虚拟头节点的下一个节点即为相加的结果
在`while l1 or l2 or carry == 1:`循环中，为什么要检查`carry == 1`？
这一检查确保即使当两个链表都已经完全遍历完毕，但仍存在一个未处理的进位（即`carry`为1）时，算法能够正确地处理这个进位。通常在最后一次链表元素相加后，如果最高位相加仍然产生了进位，我们需要添加一个额外的节点来表示这个进位，否则最终的数值会少一位，结果不正确。
你是如何处理两个链表长度不一致的情况的？
当两个链表长度不一致时，算法会继续遍历较长的链表，同时将较短链表视为已经到达尾部，其对应的数值视为0。这通过在链表遍历的`while`循环中检查`l1`和`l2`是否为`None`实现。如果一个链表已经完全遍历完毕，算法将该链表的节点值视为0，并继续处理另一个链表的剩余部分。
为什么在每次循环结束时需要更新指针`p`和`carry`？
在每次循环中，需要更新指针`p`以连接新创建的节点，这是因为我们需要构建一个新的链表来存储相加的结果。同时，更新`carry`是必要的，因为每次两个数值相加可能产生一个进位，这个进位需要在下一次循环中被加到下一位的计算中。如果不更新这两个值，我们将无法正确构建结果链表和处理进位，这将导致错误的结果。
在`if num >= 10:`判断中，为什么要将`num`减去10，并将`carry`设置为1？
这个操作是处理十进制加法中的进位情况。当两个数相加（包括进位）的结果`num`等于或大于10时，说明产生了一个进位。在这种情况下，我们需要将个位数作为新节点的值，并将高位的1作为进位传递到下一位的计算中。因此，`num`减去10后的结果是新节点的值，而将`carry`设置为1意味着下一位的计算需要加上这个进位。
为什么最终返回的是`dummy.next`而不是`dummy`？
在这个算法实现中，`dummy`节点是一个虚拟的头节点，它不存储任何实际的数据，而是用来简化链表操作，使得链表的处理逻辑更加统一和简洁。`dummy.next`指向的是链表中第一个存储实际数据的节点，因此返回`dummy.next`是返回结果链表的开始部分，而不包括没有实际意义的虚拟头节点。