难度: Medium
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0] 输出：[0]
提示：
[1, 100]0 <= node.val <= 9进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/
运行时间: 33 ms
内存: 16.1 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: ListNode, l2: ListNode) -> ListNode:
n1, n2 = [], []
while l1:
n1.append(l1.val)
l1 = l1.next
while l2:
n2.append(l2.val)
l2 = l2.next
flag = 0
res = None
while n1 or n2 or flag != 0:
s1 = n1.pop() if n1 else 0
s2 = n2.pop() if n2 else 0
ss = (s1+s2+flag)
flag = ss // 10
curnode = ListNode(ss % 10)
curnode.next = res
res = curnode
return res
本题解采用了栈的数据结构处理链表中的数字。首先，将两个链表的数字遍历并压入两个栈中，这样栈顶就代表了数字的最低位。接着，利用栈的后进先出特性，从栈顶开始逐位相加，处理进位。每次相加后，新建一个节点，将其链接到当前结果链表的头部，这样可以保持加法的顺序正确。如果最终还有进位，需要再添加一个节点处理这个进位。这种方法不需要修改原链表，符合题目的进阶要求。
时间复杂度: O(n + m)
空间复杂度: O(n + m)
# 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:
n1, n2 = [], [] # 用于存储两个链表中的数值
while l1: # 遍历链表l1，将所有数值压栈
n1.append(l1.val)
l1 = l1.next
while l2: # 遍历链表l2，将所有数值压栈
n2.append(l2.val)
l2 = l2.next
flag = 0 # 初始化进位标志
res = None # 初始化结果链表的头节点
while n1 or n2 or flag != 0: # 当栈不为空或者还有未处理的进位时继续处理
s1 = n1.pop() if n1 else 0 # 取出n1的栈顶元素，如果栈为空则用0替代
s2 = n2.pop() if n2 else 0 # 取出n2的栈顶元素，如果栈为空则用0替代
ss = (s1 + s2 + flag) # 计算当前位的和以及进位
flag = ss // 10 # 更新进位
curnode = ListNode(ss % 10) # 创建新的节点
curnode.next = res # 将新节点链接到结果链表的头部
res = curnode # 更新结果链表的头部
return res # 返回结果链表的头节点
在解决这个问题时，使用栈是因为我们需要以逆序处理两个链表中的数字，即从最低位到最高位。链表本身的结构使得直接访问最后一个元素并不容易，但栈的后进先出（LIFO）特性正好符合这一需求。如果使用数组，虽然也能实现相同的目的，但使用栈可以更直观地反映算法的逆序处理逻辑。同时，队列的先进先出（FIFO）特性并不适合这种逆序的操作需求。因此，栈是最适合这种情形的数据结构。
在算法的每次循环中，都会计算当前的总和加上进位`flag`，并更新`flag`为新的进位值（即总和除以10的商）。循环条件包括`n1`或`n2`不为空，或者`flag`不为0。这意味着即使两个栈都为空，只要`flag`为非零（即存在进位），循环将继续执行，并将这个进位作为一个新的节点添加到结果链表的头部。这样，即使在所有数字处理完毕之后仍有进位存在，也会被正确地处理并添加到结果链表中。
在Python中，整数类型（int）具有动态大小，即它们可以自动扩展以容纳较大的数值，这一特性减少了整数溢出的风险。在`ss = (s1 + s2 + flag)`这一行中，即使`s1`、`s2`和`flag`的值相对较大，整数类型也能够容纳计算结果。因此，在Python中，这行代码不会导致整数溢出问题。不过，在其他有固定整数大小限制的编程语言中，类似的操作可能需要额外的溢出处理措施。