LeetCode 2. 两数相加
LeetCode 2. 两数相加
标签
- 平台：LeetCode
- 难度：中等
- 数据结构：链表
- 算法：模拟、迭代
- 解题模式：虚拟头节点、链表合并
一、题目概述
两个非负整数用两个链表表示，链表中的每个节点保存一位数字，并且数字按逆序存放。需要返回这两个数相加后的结果链表，结果同样按逆序存放。
二、解题思路
当前实现按位模拟加法。使用两个指针 p 和 q 分别遍历两个链表，再用 carry 保存进位。每一轮取两个链表当前节点的值，如果某个链表已经结束，就按 0 处理。
为了简化结果链表的构建，代码使用 dummyHead 作为虚拟头节点，curr 始终指向结果链表的尾部。循环结束后如果还存在进位，需要额外追加一个节点。
三、执行过程
- 创建虚拟头节点
dummyHead和尾指针curr。 - 使用
p、q分别指向l1、l2。 - 当任一链表未遍历完时，取当前位数字，不存在则取
0。 - 计算
sum = x + y + carry。 - 新节点值为
sum % 10，新进位为sum / 10。 - 移动结果链表尾指针和输入链表指针。
- 循环结束后，如果
carry > 0，追加进位节点。 - 返回
dummyHead.next。
例如 2 -> 4 -> 3 和 5 -> 6 -> 4 分别表示 342 和 465，逐位相加后返回 7 -> 0 -> 8。
四、代码实现
public class LeetCode0002AddTwoNumbers {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode curr = dummyHead;
ListNode p = l1; ListNode q = l2; int carry = 0;
while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0;
int sum = x + y + carry; carry = sum / 10;
curr.next = new ListNode(sum % 10); curr = curr.next;
if (p != null) { p = p.next; } if (q != null) { q = q.next; } }
if (carry > 0) { curr.next = new ListNode(carry); }
return dummyHead.next; }}五、关键代码说明
dummyHead：虚拟头节点，用来统一处理结果链表的头节点创建。curr：结果链表的尾指针，每生成一个新节点后向后移动。p、q：分别遍历两个输入链表。carry：保存上一位产生的进位。x、y：当前位的两个数字，链表结束时按0处理。- 循环条件是
p != null || q != null，可以处理两个链表长度不同的情况。
六、复杂度分析
- 时间复杂度：
O(max(m, n))，其中m和n分别是两个链表长度。 - 空间复杂度：
O(max(m, n))，需要创建结果链表；除返回链表外，只使用常量额外变量。
七、注意事项
- 最后一位相加后仍可能产生进位，需要在循环结束后单独处理。
- 两个链表长度不一致时，短链表缺失的位置要按
0参与计算。 - 当前实现假设输入链表节点中的值是合法的一位数字。
八、面试知识点：链表与虚拟头节点
1. 为什么这题用链表模拟加法？
题目本身把数字按逆序存放在链表中，每个节点只保存一位数字，所以最自然的做法就是从链表头开始逐位相加。
因为链表头正好对应数字的最低位，当前实现不需要先反转链表，也不需要从尾部回退。只要同时遍历两个链表，并维护一个进位 carry，就能模拟小学竖式加法。
2. 为什么不能先把链表转成整数？
面试中经常会追问这个点。不能简单把链表转成 int 或 long，原因是题目没有保证数字长度一定能放进基本整数类型。
例如链表可能有几十位甚至上百位，转换成整数会溢出。链表逐位相加不依赖数字整体大小，只和链表长度有关，因此更稳妥。
3. 链表和数组有什么区别？
数组支持按下标随机访问，访问 nums[i] 是 O(1)；链表不支持高效随机访问，如果要访问第 i 个节点，需要从头走过去，时间复杂度是 O(i)。
链表的优势是插入和删除节点时不需要搬移大量元素，只要修改引用关系即可。本题中结果链表是一边计算一边追加节点，使用链表很自然。
4. 什么是虚拟头节点？
虚拟头节点也叫 dummy node。它不保存真正结果，只是放在结果链表最前面，方便统一处理链表头节点。
没有虚拟头节点时，创建第一个结果节点需要特殊判断：
如果结果链表为空，当前节点就是头节点；否则，把当前节点接到尾部。有了 dummyHead 后，每次都只需要执行：
curr.next = new ListNode(sum % 10);curr = curr.next;最后返回 dummyHead.next 即可。
5. curr 指针的作用是什么？
curr 始终指向结果链表的尾节点。每计算出一位，就把新节点挂到 curr.next，然后让 curr 后移。
这个写法的关键是：dummyHead 保持不动，用于最后返回结果；curr 负责移动，用于构建链表。如果直接移动 dummyHead，最后就找不到结果链表的头了。
6. carry 进位为什么必须保留？
链表每个节点只保存一位数字，因此当前位相加可能产生进位。
当前实现中：
int sum = x + y + carry;carry = sum / 10;curr.next = new ListNode(sum % 10);sum % 10是当前位要保存的数字；sum / 10是传给下一位的进位。
循环结束后还要检查 carry > 0。例如 5 + 5 = 10，两个链表都遍历完后，仍然要追加一个值为 1 的节点。
7. 两个链表长度不同怎么办？
当前实现用：
int x = (p != null) ? p.val : 0;int y = (q != null) ? q.val : 0;当某个链表已经遍历结束时，把它当前位当作 0。这样可以统一处理长度相同和长度不同的情况，不需要把短链表补零。
循环条件使用：
while (p != null || q != null)只要还有一个链表没走完，就继续计算。
8. 迭代和递归怎么选？
这题可以递归写，但当前实现选择迭代更直接。
迭代写法的优点是：
- 不会产生额外递归调用栈；
- 对长链表更稳定；
- 指针移动过程更容易和竖式加法对应。
递归写法通常代码更短，但需要把进位传给下一层，并且链表很长时可能有栈溢出风险。
9. 链表题常见面试追问
- 为什么链表题常用虚拟头节点？
- 什么时候返回
dummyHead.next？ - 为什么尾指针移动不能丢掉头节点？
- 如何处理空链表？
- 如何处理两个链表长度不同？
- 如何处理最后一个进位？
- 能不能原地修改其中一个链表来节省空间？
本题当前实现创建了新链表，没有修改输入链表。这种写法更清晰，也避免影响调用方继续使用原链表。
10. 回到本题，面试时怎么回答？
可以这样组织回答：
这道题本质是链表上的竖式加法。因为链表是逆序存储的，头节点就是最低位，所以我可以从两个链表头开始同时遍历。每一位计算
x + y + carry，当前节点保存sum % 10，进位保存为sum / 10。如果某个链表提前结束，就把它当前位当作0。构建结果链表时我使用虚拟头节点
dummyHead，这样可以避免单独处理第一个节点。curr指针负责不断追加结果节点，最后返回dummyHead.next。如果循环结束后还有进位，需要再追加一个节点。整体时间复杂度是O(max(m, n))，空间复杂度是O(max(m, n))。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！