难度: Medium
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912
运行时间: 56 ms
内存: 15.1 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
p1 = l1
p2 = l2
p = dummy
carry = 0
while p1 or p2 or carry != 0:
val = 0
if p1:
val += p1.val
p1 = p1.next
if p2:
val += p2.val
p2 = p2.next
if carry != 0:
val += carry
carry = 0
if val >= 10:
carry = 1
val -= 10
p.next = ListNode(val)
p = p.next
return dummy.next
该题解采用了逐位相加的方法来处理两个链表表示的数字的加法。首先，创建一个哑节点(dummy node)作为新链表的头部，用于简化边界情况的处理。两个指针p1和p2分别遍历两个链表，同时一个变量carry用于存储进位。在每一步中，将p1和p2指向的节点的值（如果存在）和carry相加，计算得到的总和如果大于等于10，则设置进位carry为1，并将总和减去10；否则，进位carry设为0。然后创建一个新节点，其值为当前位的结果，并将其加到结果链表的末尾。遍历继续，直到两个链表都完全遍历完且没有进位。最后，返回哑节点的下一个节点，即结果链表的头节点。
时间复杂度: O(max(m, n))
空间复杂度: O(max(m, n))
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # 创建哑节点作为结果链表的头部
p1 = l1 # 链表1的当前节点
p2 = l2 # 链表2的当前节点
p = dummy # 结果链表的当前节点
carry = 0 # 进位
while p1 or p2 or carry != 0:
val = 0
if p1:
val += p1.val # 添加链表1的当前节点值
p1 = p1.next # 移动到链表1的下一个节点
if p2:
val += p2.val # 添加链表2的当前节点值
p2 = p2.next # 移动到链表2的下一个节点
if carry != 0:
val += carry # 加上前一位的进位
if val >= 10:
carry = 1 # 设置新的进位
val -= 10 # 计算当前位的值
else:
carry = 0 # 清除进位
p.next = ListNode(val) # 创建新节点并连接到结果链表
p = p.next
return dummy.next # 返回结果链表的头节点
在此算法中，通过使用两个指针分别遍历两个链表，即使链表长度不相等，也能确保处理所有节点。在循环中，只要任何一个链表的指针还未遍历完或存在未处理的进位（carry != 0），循环就会继续执行。如果某个链表已经遍历完，其对应的指针会指向null，此时该链表对应数位被视为0，确保加法可以继续进行，直至两个链表都完全遍历完且没有进位。
如果在两个链表都完全遍历完毕后还存在进位，根据算法设计，我们需要添加一个额外的节点来表示这个进位。最后一次循环中，如果计算后的进位（carry）不为0，算法会创建一个新的节点，其值为此时的进位值（通常是1），并将此节点添加到结果链表的末尾。这确保了最高位的进位也被正确记录在结果链表中。
使用哑节点开始构建结果链表的主要好处是简化了代码逻辑，避免了对头节点进行特殊处理。哑节点作为结果链表的初始节点，可以在不确定第一个节点值之前就建立链表结构，避免了在循环内部需要检查并特殊处理结果链表的头节点的情况。最后返回哑节点的下一个节点作为实际的头节点，从而使整个链表的处理更加统一和简洁。
是的，这样的处理方式对所有情况都适用。在每次循环中，将两个链表的相应数位和已有的进位值相加。如果这个总和小于10，则不需要进位，因此将进位（carry）设置为0。如果总和大于或等于10，则生成一个新的进位（通常设置为1），并调整当前位的数值（总和减10）。这样的逻辑确保了每一位的正确计算，同时进位也得到了正确的处理。