445. 两数相加 II
题目描述
输入两个非空链表 l1 和 l2，各自表示一个非负整数。每个节点存一位数字，表头是最高位，表尾是个位。链表以数组形式给出，例如 [7,2,4,3] 表示 7243。
求两数之和，并用同样的形式（高位在前、每节点一位）构造新链表返回。
除了数本身就是 0 的情况，两个数都没有前导零。
示例 1
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
解释：7243 + 564 = 7807。
示例 2
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
解释：243 + 564 = 807。
示例 3
输入：l1 = [0], l2 = [0] 输出：[0]
解释：0 + 0 = 0。
数据范围
- 每个链表的节点数在
[1, 100]范围内。 0 <= node.val <= 9- 链表表示的数字不含前导零。
进阶：如果不允许把输入链表反转，应当怎么做？
解题思路：栈
加法要从个位算起，而链表只能从高位往后走。把两条链表的值分别压进栈 s1、s2，栈顶就是个位。然后每轮各弹出一位（空栈按 0 算），加上进位得到 total，新节点存 total % 10，进位更新为 total // 10。因为先算出的是低位，新节点要用头插法放到结果链表最前面。
为什么正确
每轮结束时，head 开始的链表恰好是已经算出的低几位之和（高位在前），carry 是要带给更高一位的进位。
复杂度分析
时间 O(m+n)，两个栈占 O(m+n) 额外空间（m、n 为两条链表长度）。
易错点
循环条件要写成 s1 or s2 or carry。漏掉 carry 时，像 999 + 1 这样最高位进位的情况会少一个 1。另外，结果要头插，不能尾插，否则得到的数字是反的。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
head, carry = None, 0
while s1 or s2 or carry:
a = s1.pop() if s1 else 0
b = s2.pop() if s2 else 0
total = a + b + carry
carry = total // 10
node = ListNode(total % 10)
node.next = head
head = node
return headclass Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
while (l1 != null) {
s1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
s2.push(l2.val);
l2 = l2.next;
}
ListNode head = null; int carry = 0;
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
int a = s1.isEmpty() ? 0 : s1.pop();
int b = s2.isEmpty() ? 0 : s2.pop();
int total = a + b + carry;
carry = total / 10;
ListNode node = new ListNode(total % 10);
node.next = head;
head = node;
}
return head;
}
}class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
vector<int> s1, s2;
while (l1) {
s1.push_back(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push_back(l2->val);
l2 = l2->next;
}
ListNode* head = nullptr; int carry = 0;
while (!s1.empty() || !s2.empty() || carry) {
int a = 0; if (!s1.empty()) { a = s1.back(); s1.pop_back(); }
int b = 0; if (!s2.empty()) { b = s2.back(); s2.pop_back(); }
int total = a + b + carry;
carry = total / 10;
ListNode* node = new ListNode(total % 10);
node->next = head;
head = node;
}
return head;
}
};func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
s1, s2 := []int{}, []int{}
for l1 != nil {
s1 = append(s1, l1.Val)
l1 = l1.Next
}
for l2 != nil {
s2 = append(s2, l2.Val)
l2 = l2.Next
}
var head *ListNode; carry := 0
for len(s1) > 0 || len(s2) > 0 || carry > 0 {
a := 0; if len(s1) > 0 { a = s1[len(s1)-1]; s1 = s1[:len(s1)-1] }
b := 0; if len(s2) > 0 { b = s2[len(s2)-1]; s2 = s2[:len(s2)-1] }
total := a + b + carry
carry = total / 10
node := &ListNode{Val: total % 10}
node.Next = head
head = node
}
return head
}var addTwoNumbers = function(l1, l2) {
const s1 = [], s2 = [];
while (l1) {
s1.push(l1.val);
l1 = l1.next;
}
while (l2) {
s2.push(l2.val);
l2 = l2.next;
}
let head = null, carry = 0;
while (s1.length || s2.length || carry) {
const a = s1.length ? s1.pop() : 0;
const b = s2.length ? s2.pop() : 0;
const total = a + b + carry;
carry = Math.floor(total / 10);
const node = new ListNode(total % 10);
node.next = head;
head = node;
}
return head;
};function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const s1: number[] = [], s2: number[] = [];
while (l1) {
s1.push(l1.val);
l1 = l1.next;
}
while (l2) {
s2.push(l2.val);
l2 = l2.next;
}
let head: ListNode | null = null, carry = 0;
while (s1.length || s2.length || carry) {
const a = s1.length ? s1.pop()! : 0;
const b = s2.length ? s2.pop()! : 0;
const total = a + b + carry;
carry = Math.floor(total / 10);
const node = new ListNode(total % 10);
node.next = head;
head = node;
}
return head;
};其他解法
栈法不改动输入，但要 O(m+n) 辅助空间；反转法省空间，代价是破坏原链表。
解法 2：反转链表后相加 时间 O(m+n)，空间 O(1)
先把两条链表原地反转，让个位在前。然后像第 2 题一样逐位相加，处理进位。每算出一位就用头插法放在结果链表最前面，结果自然是高位在前，不需要再反转。
除结果外只用 O(1) 额外空间。会修改输入链表；若题目要求不能修改输入（进阶要求），就不适用。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
# 反转后低位在前，可以像第 2 题一样逐位相加
a, b = reverse(l1), reverse(l2)
head, carry = None, 0
while a or b or carry:
total = carry
if a:
total += a.val
a = a.next
if b:
total += b.val
b = b.next
carry = total // 10
# 头插法：新算出的位更高，放在最前面
head = ListNode(total % 10, head)
return headclass Solution {
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nxt = head.next;
head.next = prev;
prev = head;
head = nxt;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode a = reverse(l1), b = reverse(l2);
ListNode head = null;
int carry = 0;
while (a != null || b != null || carry != 0) {
int total = carry;
if (a != null) { total += a.val; a = a.next; }
if (b != null) { total += b.val; b = b.next; }
carry = total / 10;
head = new ListNode(total % 10, head);
}
return head;
}
}class Solution {
public:
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* nxt = head->next;
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* a = reverse(l1);
ListNode* b = reverse(l2);
ListNode* head = nullptr;
int carry = 0;
while (a || b || carry) {
int total = carry;
if (a) { total += a->val; a = a->next; }
if (b) { total += b->val; b = b->next; }
carry = total / 10;
head = new ListNode(total % 10, head);
}
return head;
}
};func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
reverse := func(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
nxt := head.Next
head.Next = prev
prev = head
head = nxt
}
return prev
}
a, b := reverse(l1), reverse(l2)
var head *ListNode
carry := 0
for a != nil || b != nil || carry != 0 {
total := carry
if a != nil {
total += a.Val
a = a.Next
}
if b != nil {
total += b.Val
b = b.Next
}
carry = total / 10
head = &ListNode{Val: total % 10, Next: head}
}
return head
}var addTwoNumbers = function(l1, l2) {
const reverse = (head) => {
let prev = null;
while (head) {
const nxt = head.next;
head.next = prev;
prev = head;
head = nxt;
}
return prev;
};
let a = reverse(l1), b = reverse(l2);
let head = null, carry = 0;
while (a || b || carry) {
let total = carry;
if (a) { total += a.val; a = a.next; }
if (b) { total += b.val; b = b.next; }
carry = Math.floor(total / 10);
head = new ListNode(total % 10, head);
}
return head;
};function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const reverse = (head: ListNode | null): ListNode | null => {
let prev: ListNode | null = null;
while (head) {
const nxt: ListNode | null = head.next;
head.next = prev;
prev = head;
head = nxt;
}
return prev;
};
let a = reverse(l1), b = reverse(l2);
let head: ListNode | null = null;
let carry = 0;
while (a || b || carry) {
let total = carry;
if (a) { total += a.val; a = a.next; }
if (b) { total += b.val; b = b.next; }
carry = Math.floor(total / 10);
head = new ListNode(total % 10, head);
}
return head;
}