LeetCode 2. 两数相加
题目描述
✅ 2. 两数相加
题意分析
两条非空链表分别表示两个非负整数，每个节点只保存一位数字，且数字按逆序排列：头节点是个位，后面依次是十位、百位。需要返回一条同样按低位到高位排列的链表，表示两数之和。
两条链表不一定等长，较短链表没有的高位按
0参与运算。结果也可能比两个输入都多一位，因为最高位相加后仍可能产生进位。链表最多有 100 个节点，不能依赖普通整数容纳整个数；逐位计算即可处理任意合法长度。
解法：逐位相加维护进位
核心思路
[!blue]
加法从低位开始，因为高位的结果依赖低位传来的进位。题目恰好把低位放在链表前面，所以直接从头向后遍历，不需要反转链表。
用
carry保存上一位传来的进位。每轮把两个当前节点的值与carry相加，得到sum；缺失的节点按0处理。sum % 10是当前结果位，sum / 10是要交给下一位的进位。每个输入数字最多是9，因此sum最多为19，进位只可能是0或1。结果链表始终保存已经算好的低位，
tail指向末尾。追加当前位后，低位部分就完全确定，下一轮只需要处理更高位及新的carry，无需回头修改已生成的节点。只要任意输入还有节点，或者仍有进位，就还存在未处理的数值。两条链表都耗尽后若
carry为1，还要单独生成最高位节点；只有三个条件都不满足时才能结束。哨兵节点dummy仅用于统一追加操作，真正的结果从dummy.next开始。
解题步骤
- 创建哨兵节点
dummy，令tail = dummy、carry = 0。- 当任意链表未结束或
carry != 0时，将sum初始化为进位。- 对每条尚未结束的链表，加上当前节点值，并把指针移到下一节点。
- 在结果末尾追加值为
sum % 10的新节点，移动tail，更新carry = sum / 10。- 循环结束后返回
dummy.next，跳过不属于答案的哨兵节点。
代码实现
class 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 sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
// 本位写入新节点，下一位只继承商作为进位。
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
}
return dummy.next;
}
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
// 两条链表耗尽后，最高位进位仍需生成一个节点。
for l1 != nil || l2 != nil || carry != 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
// 本位写入新节点，下一位只继承商作为进位。
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}
复杂度分析
设两条链表的长度分别为 $m$、$n$。
- 时间复杂度：$O(\max(m, n))$。每个输入节点访问一次，最后的进位最多增加一轮。
- 辅助空间复杂度：$O(1)$，只维护几个指针和进位；返回的结果链表占 $O(\max(m, n))$ 空间，不计入辅助空间。
关键点总结
[!green]
- 逆序存储与从低位到高位的进位方向一致，可以直接同步遍历。
- 每轮只把当前位写入结果，尚未处理的影响全部由
carry传给下一轮。- 链表长度不等和最终多出一位，都由同一个循环条件统一处理。
易错点总结
[!yellow]
- 循环条件使用
&&会在较短链表结束时提前退出；两条链表和进位之间应使用||。- 只判断两条链表是否结束，会遗漏最后的最高位进位。
- 不能在短链表结束后直接接上另一条链表的剩余部分：当前进位可能继续改变后续数字。
% 10得到当前位，/ 10得到下一位进位，不能交换。- 忘记移动输入指针会重复计算同一位，忘记移动
tail会覆盖已接上的节点；返回时也必须跳过dummy。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 445. 两数相加 II | 中等 | 加法规则相同，原题高位在链头，需栈或反转后才能先处理低位。 |
| 415. 字符串相加 | 简单 | 同样逐位求和与进位，字符串从末尾读取，本题链表已经按低位在前排列。 |
| 66. 加一 | 简单 | 逐位计算并维护进位；本题链表低位在前可直接遍历相加，该题加一时只传播单次进位。 |
| 67. 二进制求和 | 简单 | 逐位计算并维护进位；本题链表低位在前可直接遍历相加，该题按二进制位相加。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！