题目概览
范围
| 来源 | 内容 |
|---|---|
class011 | AddTwoNumbers |
题型归纳
题型： 链表模拟加法
适用条件： 两个链表按逆序存储数字，每个节点只表示一位数字。
解法： 从两个链表头节点开始逐位相加，同时维护进位 carry，每一位生成一个新节点。
易错点： 两个链表长度不同、最后还有进位、空指针取值、返回结果链表头节点。
看到”链表逆序存储数字、需要模拟加法”就是这种写法的信号——因为头节点恰好是个位，逆序存储反而省去了反转的麻烦，可以直接从头往后扫。核心做法是逐位求
sum = h1.val + h2.val + carry，当前位取sum % 10，进位取sum / 10；最容易出错的是循环条件写成&&导致漏算较长链表的高位，以及循环结束后忘记补最后一个进位节点。
例题：2. 两数相加
题意
给定两个非空链表 l1 和 l2，分别表示两个非负整数，数字按逆序存储，每个节点只存一位。把两个数相加后，用同样的逆序链表形式返回结果。
示例
示例 1：
输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807
示例 2：
输入： l1 = [0], l2 = [0]
输出： [0]
示例 3：
输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]
提示
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
解法
核心思路
这道题本质就是竖式加法，只是数字已经用链表逆序存好了。
因为头节点就是个位，所以可以直接从两个链表头部开始往后走，逐位求和：当前位的结果是 sum % 10，新的进位是 sum / 10，已经为空的链表在后续计算中按 0 处理。
链表逆序存储不是麻烦，而是恩赐——个位在头节点，天然对齐竖式加法的计算顺序，不需要任何反转。
核心模板
public static ListNode addTwoNumbers(ListNode h1, ListNode h2) { ListNode ans = null; ListNode cur = null; int carry = 0;
for (int sum, val; h1 != null || h2 != null; h1 = h1 == null ? null : h1.next, h2 = h2 == null ? null : h2.next) {
sum = (h1 == null ? 0 : h1.val) + (h2 == null ? 0 : h2.val) + carry; val = sum % 10; carry = sum / 10;
if (ans == null) { ans = new ListNode(val); cur = ans; } else { cur.next = new ListNode(val); cur = cur.next; } }
if (carry == 1) { cur.next = new ListNode(1); } return ans;}变量角色
h1 和 h2 分别指向两条链表当前正在相加的节点；ans 记住答案链表的头节点，最终返回它；cur 始终指向答案链表的尾节点，每生成一个新节点就跟着往后移动一位——ans 和 cur 初始都为 null，第一次生成节点时同时赋值，之后只动 cur，不动 ans。
过程拆解
- 逐位求和：每轮取
h1.val（为空按0）、h2.val（为空按0）和carry求和。 - 生成节点：
val = sum % 10作为当前节点值，更新carry = sum / 10。 - 接入链表：第一个节点同时赋给
ans和cur，后续接到cur.next，再移动cur。 - 推进指针：
h1和h2各自向后移动，已为空的继续保持null。 - 补进位：循环结束后如果
carry == 1，在cur后面补一个值为1的节点。
易错点
- 第一次创建节点时，
ans和cur都要赋值；之后只移动cur，ans不能动，否则最终找不到链表头。
循环条件写成&&会漏算高位错误写法：
为什么错：较短链表走完后循环立即停止，较长链表剩余的高位全部丢失。比如
l1 = [1]、l2 = [9,9]，正确结果是[0,0,1]，用&&只会得到[0]。正确写法：
两条链表都走完才停，已经为空的那条当前位按
0处理。
循环结束后忘记补进位节点错误写法：直接
return ans，不检查carry。为什么错：最高位相加可能产生进位。比如
l1 = [9]、l2 = [9]，当前位结果是8，carry = 1，正确答案是[8,1]，漏掉进位会返回[8]。正确写法：
口诀
||控制循环，空链表按0，循环后补进位。
复杂度
- 时间复杂度：
O(max(n, m))，n和m分别是两个链表的长度 - 空间复杂度：
O(max(n, m))，答案链表需要保存相加结果
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时