Add Two Numbers
你会得到两个非负整数，每个整数都以单向链表存储各位数字，最低位在前。在第一个链表中，节点 i 存储数字 values1[i]，并链接到节点 next1[i]。第二个链表的结构相同，使用 next2 和 values2。两个链表中，-1 都表示链表结束，头节点都是节点 0。节点的存储顺序与链表顺序不同，因此要沿着链接遍历。
返回两个数的和的各位数字，最低位在前。
函数
- next1integer-array
- 第一个数字中每个节点所链接节点的索引；如果是最后一个节点，则为 -1
- values1integer-array
- 第一个数字中每个节点保存的数字
- next2integer-array
- 第二个数字中每个节点所链接到的节点索引；如果是最后一个节点，则为 -1
- values2integer-array
- 第二个数字中每个节点保存的数字
- 返回值integer-array
- 总和的各位数字，按从低位到高位排列
约束条件
1 ≤ L1 ≤ 100，其中L1是next1和values1的长度。1 ≤ L2 ≤ 100，其中L2是next2和values2的长度。0 ≤ values1[i], values2[j] ≤ 9-
next1的每个条目都是-1或第一个列表的节点索引，next2的每个条目都是-1或第二个列表的节点索引。 - 从节点
0开始，每个列表都会恰好访问其中的每个节点一次，然后到达-1。不存在循环。 - 没有任何数字以零开头：列表的最后一个节点保存的数字不是
0，除非列表只有一个数字0。
示例
- 输入
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- 输出
- [5, 4, 1, 1]
- 解释
- 第一个列表访问节点
0, 2, 1，并读取8, 1, 6，组成数字 618。第二个列表读取7, 2, 5，组成数字 527。它们的和是 1145，所以答案是5, 4, 1, 1。
- 输入
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- 输出
- [0, 0, 0, 0, 1]
- 解释
- 第二个列表表示
1, 9, 9, 9，也就是数字 9991。加上 9 后得到 10000：每一位都会产生一个0和一个进位，最后的进位会成为第五位。
- 输入
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- 输出
- [7, 5]
- 解释
- 第一个数是 0，第二个列表读作
7, 5，也就是数字 57。加上 0 不会改变任何内容，所以答案是[7, 5]。
进阶
如果列表按最高位在前的顺序存储数字，你会如何将这些数字相加？
提示
逐个打开提示，每个都会多透露一点。
把每个列表都转换成一个数字会失败：100 位数字无法放进任何整数类型中。你在纸上是怎么把两个大数相加的？
列表从个位开始，这正是竖式加法的起始位置。每一列都将两个数各自的一位数字与前一列的进位相加。该列写下
sum % 10，并将sum / 10向下取整后进位。用两个指针同时遍历两个列表。如果某个列表已经遍历完，就加上
0。只要任一指针不等于-1，或者进位为1，就继续遍历，这样最后的进位就会成为多出的一个数字。
题解
这些数字太长，无法用任何整数类型表示，所以要像在纸上一样把它们相加：按列相加，当某一列的和达到 10 时，就进 1。列表把个位数字存放在最前面，因此遍历列表时，访问各列的顺序正好就是相加的顺序。
先把数字抄出来，然后逐列相加
思路
这里的指针是节点索引，向前移动就是 node = next[node]。把每个列表中的数字复制到数组中，让索引 i 表示权重为 10^i 的数字：第一个示例中是 [8, 1, 6] 和 [7, 2, 5]。
然后像在纸上计算一样相加，缺少的数字按 0 计算。每一列写下 sum % 10，并把其余部分进位：8 + 7 = 15，写下 5 并进位 1；1 + 2 + 1 = 4；6 + 5 = 11，写下 1。最后的进位成为最后一位数字：[5, 4, 1, 1]。
复制操作会额外占用 O(L1 + L2) 内存，而加法本身并不需要这些内存。
算法
- 从节点
0开始遍历每个列表，并将其中的数字复制到数组中。 - 设置
carry = 0。对于不超过较长数组长度的每个索引i，将存在的索引i处的数字与进位相加。 - 追加
sum % 10，并将carry设置为sum / 10向下取整后的结果。 - 如果最后一列处理完后进位为
1，则追加它。
def readDigits(next, values):
# The digits in list order: least significant first.
digits = []
node = 0
while node != -1:
digits.append(values[node])
node = next[node]
return digits
def addTwoNumbers(next1, values1, next2, values2):
first = readDigits(next1, values1)
second = readDigits(next2, values2)
result = []
carry = 0
for i in range(max(len(first), len(second))):
column = carry
if i < len(first):
column += first[i]
if i < len(second):
column += second[i]
result.append(column % 10)
carry = column // 10
if carry > 0:
result.append(carry)
return result同时遍历两个列表，并记录进位
思路
第 i 列只使用每个列表中的第 i 个节点，所以为每个列表保留一个指针，分别是 a 和 b，并随着列的推进移动这两个指针。
当 a 不等于 -1、b 不等于 -1，或进位为 1 时，循环会继续运行。有节点的指针会加上该节点的数字，然后向前移动；指向 -1 的指针则不加任何值。这样无需再写一个循环，就能处理长度不同的数字；进位条件则会在末尾写入多出来的数字。
在第二个示例中，9 加 9991 时，每一列的和都是 10，因此会写入 0。四列处理完后，两个列表都已结束，但进位仍为 1，所以循环还会再运行一次，得到 [0, 0, 0, 0, 1]。除答案外，它还只使用了三个整数。
算法
- 将
a = 0、b = 0和carry = 0设为初始值。 - 当
a != -1或b != -1或carry > 0时，将列求和的初始值设为carry。 - 如果
a != -1，就加上values1[a]，并将a设为next1[a]。对第二个列表中的b执行相同操作。 - 追加
sum % 10，并将carry设为sum / 10向下取整后的值。 - 返回你追加的数字。
def addTwoNumbers(next1, values1, next2, values2):
a = 0 # current node of the first number
b = 0 # current node of the second number
carry = 0
result = []
# Keep going while either number has digits left or a carry is waiting.
while a != -1 or b != -1 or carry > 0:
column = carry
if a != -1:
column += values1[a]
a = next1[a]
if b != -1:
column += values2[b]
b = next2[b]
result.append(column % 10) # the digit this column writes
carry = column // 10 # 1 when the column reached 10, else 0
return result
易错点和边界情况
- 将每个列表转换为整数再相加。100 位数会超出任何 64 位类型的范围。
- 丢掉最后的进位。如果循环在两个列表都结束时停止，那么第二个示例会返回
[0, 0, 0, 0]。 - 在较短的列表结束时停止。这样，第二个示例会丢失 9991 中的 3 个 9，以及在它们之间传递的进位。
- 按数组顺序读取数字。在第一个示例中，
values1是[8, 6, 1]，但沿着链接读取时，数字是 618。 - 忘记 Lua 和 R 中的偏移量，数组从 1 开始。节点 ID 保持从 0 开始，并读取
next1[node + 1]。
常见问题3
为什么在“两个数相加”中，数字是按逆序存储的？
加法从个位开始，而单向链表只能从头节点开始遍历。最低位在前时，遍历顺序与加法的列顺序一致，因此进位会随着指针向前传递。
将两个以链表形式存储的数字相加，时间复杂度是多少？
它的时间复杂度是 O(max(L1, L2))：每列执行一步，如果最后还剩进位，则再执行一步。除答案外，单次遍历版本使用 O(1) 的内存：两个指针和进位。
进位可能大于 1 吗？
不会。一列最多把两个不超过 9 的数字和一个不超过 1 的进位相加，因此总和最多为 19。除以 10 并向下取整，结果为 0 或 1。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def addTwoNumbers(next1, values1, next2, values2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
预期输出
[5, 4, 1, 1]