2. 两数相加
题目描述
输入两个非空链表 l1 和 l2，各自表示一个非负整数。链表从头到尾依次存放该数的个位、十位、百位……，每个节点只放一位数字。
把这两个整数相加，用同样的逆序链表形式返回它们的和。
除了数字 0 本身，两个数都没有前导零。
示例 1
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8]
解释：两数分别是 342 和 465，和为 807，逆序存放就是 [7,0,8]。
示例 2
输入：l1 = [0], l2 = [0] 输出：[0]
解释：0 + 0 = 0。
示例 3
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
解释：9999999 + 9999 = 10009998，逆序存放为 [8,9,9,9,0,0,0,1]。
数据范围
- 每个链表的节点数在
[1, 100]之间 0 <= Node.val <= 9- 链表表示的数没有前导零。
解题思路：逐位模拟（迭代）
逐位加两个节点值及进位，用 divmod 同时计算新进位和个位。
为什么正确
结果前缀已经正确表示所有处理过的低位，carry 是传给下一位的进位。
复杂度分析
时间 O(max(m,n))，额外空间 O(1)，输出空间 O(max(m,n))。
易错点
循环条件必须包括 carry，否则会漏掉最高位进位。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = ListNode(0)
tail = dummy
carry = 0
while l1 or l2 or carry:
total = carry
if l1:
total += l1.val
l1 = l1.next
if l2:
total += l2.val
l2 = l2.next
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
return dummy.nextclass Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int total = carry;
if (l1 != null) {
total += l1.val;
l1 = l1.next;
}
if (l2 != null) {
total += l2.val;
l2 = l2.next;
}
int digit = total % 10;
carry = total / 10;
tail.next = new ListNode(digit);
tail = tail.next;
}
return dummy.next;
}
}class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int total = carry;
if (l1) {
total += l1->val;
l1 = l1->next;
}
if (l2) {
total += l2->val;
l2 = l2->next;
}
int digit = total % 10;
carry = total / 10;
tail->next = new ListNode(digit);
tail = tail->next;
}
return dummy->next;
}
};func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
total := carry
if l1 != nil {
total += l1.Val
l1 = l1.Next
}
if l2 != nil {
total += l2.Val
l2 = l2.Next
}
digit := total % 10
carry = total / 10
tail.Next = &ListNode{Val: digit}
tail = tail.Next
}
return dummy.Next
}var addTwoNumbers = function(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (l1 || l2 || carry) {
let total = carry;
if (l1) {
total += l1.val;
l1 = l1.next;
}
if (l2) {
total += l2.val;
l2 = l2.next;
}
const digit = total % 10;
carry = Math.floor(total / 10);
tail.next = new ListNode(digit);
tail = tail.next;
}
return dummy.next;
};function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (l1 || l2 || carry) {
let total = carry;
if (l1) {
total += l1.val;
l1 = l1.next;
}
if (l2) {
total += l2.val;
l2 = l2.next;
}
const digit = total % 10;
carry = Math.floor(total / 10);
tail.next = new ListNode(digit);
tail = tail.next;
}
return dummy.next;
};其他解法
两种做法都逐位相加并传递进位；迭代版额外空间 O(1)，递归版写法更贴近定义但需要调用栈。
解法 2：递归逐位相加 时间 O(max(m,n))，空间 O(max(m,n))
定义 add(a, b, carry)：返回两条剩余链表加上进位后的结果链表。三者都为空时返回空。否则算出当前位 total，新建节点存 total % 10，它的 next 交给 add(a.next, b.next, total / 10)。
不需要哑节点和尾指针，代码直接对应“当前位 + 剩余部分”的定义。递归深度等于结果长度，占用 O(max(m,n)) 栈空间。
class Solution:
def addTwoNumbers(self, l1, l2):
def add(a, b, carry):
if not a and not b and not carry:
return None
total = carry
if a:
total += a.val
a = a.next
if b:
total += b.val
b = b.next
node = ListNode(total % 10)
node.next = add(a, b, total // 10)
return node
return add(l1, l2, 0)class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return add(l1, l2, 0);
}
private ListNode add(ListNode a, ListNode b, int carry) {
if (a == null && b == null && carry == 0) return null;
int total = carry;
if (a != null) {
total += a.val;
a = a.next;
}
if (b != null) {
total += b.val;
b = b.next;
}
ListNode node = new ListNode(total % 10);
node.next = add(a, b, total / 10);
return node;
}
}class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return add(l1, l2, 0);
}
ListNode* add(ListNode* a, ListNode* b, int carry) {
if (!a && !b && !carry) return nullptr;
int total = carry;
if (a) {
total += a->val;
a = a->next;
}
if (b) {
total += b->val;
b = b->next;
}
ListNode* node = new ListNode(total % 10);
node->next = add(a, b, total / 10);
return node;
}
};func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
return addRec(l1, l2, 0)
}
func addRec(a, b *ListNode, carry int) *ListNode {
if a == nil && b == nil && carry == 0 {
return nil
}
total := carry
if a != nil {
total += a.Val
a = a.Next
}
if b != nil {
total += b.Val
b = b.Next
}
node := &ListNode{Val: total % 10}
node.Next = addRec(a, b, total/10)
return node
}var addTwoNumbers = function(l1, l2) {
const add = (a, b, carry) => {
if (!a && !b && !carry) return null;
let total = carry;
if (a) {
total += a.val;
a = a.next;
}
if (b) {
total += b.val;
b = b.next;
}
const node = new ListNode(total % 10);
node.next = add(a, b, Math.floor(total / 10));
return node;
};
return add(l1, l2, 0);
};function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const add = (a: ListNode | null, b: ListNode | null, carry: number): ListNode | null => {
if (!a && !b && !carry) return null;
let total = carry;
if (a) {
total += a.val;
a = a.next;
}
if (b) {
total += b.val;
b = b.next;
}
const node = new ListNode(total % 10);
node.next = add(a, b, Math.floor(total / 10));
return node;
};
return add(l1, l2, 0);
};