网硕互联帮助中心1. 题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 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]
2. 题解
2.1. 模拟
2.1.1. 核心思想
模拟人工竖式加法，从低位到高位逐位相加，保存进位，只要还有链表节点或者还有进位，就继续生成结果节点。
关键点拆解
链表是逆序：链表头部天然对应数字最低位，直接从头遍历就是从个位开始相加，不需要反转链表。
进位 carry：每一位总和 = l1 当前位 + l2 当前位 + 上一轮进位
- 当前位值：sum % 10
- 新进位：sum / 10
长短链表兼容：某一条链表遍历完之后，该链表取值当作 0，不用单独写一大段分支处理剩余链表。
循环终止条件（非常关键）
p1不为空 OR p2不为空 OR carry>0
即使两条链表都走完，如果进位还有 1（例如 999+999 最后进位 1），必须再新建一个节点保存最高进位。
虚拟头结点 (dummy 哑节点)
- 消除 “是否是第一个节点” 的特殊判断，头节点、普通节点统一用 tail->next = new ListNode() 生成。
- dummy 本身无意义，返回 dummy->next 作为真实结果头。
2.1.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
ListNode* p1 = l1;
ListNode* p2 = l2;
int carry = 0; // 进位
// 只要p1不为空 或者 p2不为空 或者还有进位，就要继续建节点
while (p1 != nullptr || p2 != nullptr || carry != 0) {
int v1 = p1 ? p1->val : 0;
int v2 = p2 ? p2->val : 0;
int sum = v1 + v2 + carry;
carry = sum / 10;
int curVal = sum % 10;
// 堆上新建节点，不能栈对象！
tail->next = new ListNode(curVal);
tail = tail->next;
if(p1) p1 = p1->next;
if(p2) p2 = p2->next;
}
// dummy是虚拟头，真正结果从dummy->next开始
return dummy->next;
}
};
2.1.3. 复杂度
时间复杂度：
O
(
max
(
n
,
m
)
)
O(\\max(n,m))
O(max(n,m))，n、m 是两个链表长度，最多遍历较长链表 + 一次进位。 空间复杂度：
O
(
max
(
n
,
m
)
)
O(\\max(n,m))
O(max(n,m))，新建结果链表；不算输出链表空间则为
(
O
(
1
)
(O(1)
(O(1)。
评论前必须登录！
注册