LeetCode 445 题解：两数相加 II——用栈与反转破解“高位在前“的链表加法

LeetCode 445 题解：两数相加 II——用栈与反转破解"高位在前"的链表加法

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇文章基于开源仓库 leetcode 中的题解文档 problems/445.add-two-numbers-ii.md，围绕 LeetCode 445「两数相加 II」展开：数字按高位在前（顺序存储）的方式存入链表，要求两数相加并返回同样高位在前的结果链表。读完本文你将掌握两种核心解法——利用栈将链表逆序处理的"栈解法"，以及"先反转、相加、再反转"的经典套路，并能独立写出 JS、C++、Python3 三版 bug-free 代码。

题目描述与核心难点

题目要求：给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置，每个节点只存储一位数字。将这两数相加后返回一个新的链表。

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7

（原因：7243 + 564 = 7807）

两个隐含条件需要注意：

• 除了数字 0 之外，这两个数字都不会以零开头；
• 进阶：如果输入链表不能修改该如何处理？即不能对链表中的节点进行翻转。

本题的关键难点在于链表是高位在前的顺序存储，而两数相加必须从低位（链尾）开始，逐位相加并处理进位。单链表只能从头部向尾部单向遍历，无法直接"从后往前"访问节点——这与数字存储顺序天然相悖，因此需要借助数据结构或算法技巧来翻转访问顺序。

前置知识与考点

• 链表：单链表节点的基本结构、遍历方式，以及"增删操作依赖前驱节点"的特性；
• 栈：后进先出（LIFO）特性恰好能把链表从尾到头"倒着读"出来。

结合仓库 thinkings/linked-list.md 的链表专题总结，本题同时命中其中的"一个原则、两个考点"：考察点集中在指针的修改与链表的拼接（求和结果的链表重建本质上就是节点拼接），而"画图、聚焦子结构"则是避免指针操作出错的最实用技巧。

解法一：栈解法（不修改输入链表）

思路

利用栈的"后进先出"特性，将两个链表的值分别从前往后依次入栈：

1. 依次将链表 l1 的节点值入栈 stack1，链表 l2 的节点值入栈 stack2；
2. 同时从 stack1、stack2 弹栈（即从低位开始），逐位相加并处理进位，把当前位的结果入栈 stack；
3. 用一个 carried 变量记录进位；
4. 循环结束后，将 stack 依次弹出并重建链表，即可得到高位在前的结果。

栈解法天然满足进阶要求：不修改原链表，仅借助额外空间完成逆序访问。

关键点解析

• 栈的基本操作：push 入栈、pop 弹栈，模拟"从尾到头"的访问顺序；
• carried 变量记录进位：每一位的和为a + b + carried，当前位存入(a + b + carried) % 10，进位更新为(a + b + carried) >= 10 ? 1 : 0；
• 循环终止条件设为stack.length > 0可以简化操作，不用分别处理两个栈谁先弹空的边界；
• 注意特殊情况：例如1 + 99 = 100，两个栈弹空后仍可能有进位 1，必须在循环结束后单独判断并补一个最高位节点。

JavaScript 实现

/* * @lc app=leetcode id=445 lang=javascript * * [445] Add Two Numbers II */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function (l1, l2) { const stack1 = []; const stack2 = []; const stack = []; let cur1 = l1; let cur2 = l2; let curried = 0; while (cur1) { stack1.push(cur1.val); cur1 = cur1.next; } while (cur2) { stack2.push(cur2.val); cur2 = cur2.next; } let a = null; let b = null; while (stack1.length > 0 || stack2.length > 0) { a = Number(stack1.pop()) || 0; b = Number(stack2.pop()) || 0; stack.push((a + b + curried) % 10); if (a + b + curried >= 10) { curried = 1; } else { curried = 0; } } if (curried === 1) { stack.push(1); } const dummy = {}; let current = dummy; while (stack.length > 0) { current.next = { val: stack.pop(), next: null, }; current = current.next; } return dummy.next; };

代码中的两个细节值得注意：

• Number(stack1.pop()) || 0：当某个栈先弹空时，pop 返回undefined，Number(undefined) || 0兜底为 0，保证两个链表长度不一致时也能正确相加；
• 结果栈 stack 中的顺序是"高位在栈底、低位在栈顶"，重建链表时依次 pop，恰好恢复高位在前的顺序；
• dummy虚拟头节点与 thinkings/linked-list.md 中总结的"虚拟头技巧"一致——将头节点变成中间节点，简化边界判断，最后返回dummy.next即可。

C++ 实现（栈版本）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { auto carry = 0; auto ret = (ListNode*)nullptr; auto s1 = vector<int>(); toStack(l1, s1); auto s2 = vector<int>(); toStack(l2, s2); while (!s1.empty() || !s2.empty() || carry != 0) { auto v1 = 0; auto v2 = 0; if (!s1.empty()) { v1 = s1.back(); s1.pop_back(); } if (!s2.empty()) { v2 = s2.back(); s2.pop_back(); } auto v = v1 + v2 + carry; carry = v / 10; auto tmp = new ListNode(v % 10); tmp->next = ret; ret = tmp; } return ret; } private: // 此处若返回而非传入vector，跑完所有测试用例多花8ms void toStack(const ListNode* l, vector<int>& ret) { while (l != nullptr) { ret.push_back(l->val); l = l->next; } } };

C++ 版本的实现差异值得玩味：

• while 条件把carry != 0直接纳入循环：这样循环结束后无需再单独判断进位，1 + 99 = 100这类最高位进位的情况被统一处理；
• tmp->next = ret; ret = tmp;采用头插法：每一位计算出的结果节点直接插到当前结果链表的头部，天然实现了结果的逆序恢复，无需额外使用结果栈；
• 注释里给出了一个实测优化细节：toStack用传引用返回 vector而非直接返回 vector，跑完所有测试用例能省约 8ms——这是 C++ 避免拷贝开销的实用经验。

Python3 实现

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: def listToStack(l: ListNode) -> list: stack, c = [], l while c: stack.append(c.val) c = c.next return stack # transfer l1 and l2 into stacks stack1, stack2 = listToStack(l1), listToStack(l2) # add stack1 and stack2 diff = abs(len(stack1) - len(stack2)) stack1 = ([0]*diff + stack1 if len(stack1) < len(stack2) else stack1) stack2 = ([0]*diff + stack2 if len(stack2) < len(stack1) else stack2) stack3 = [x + y for x, y in zip(stack1, stack2)] # calculate carry for each item in stack3 and add one to the item before it carry = 0 for i, val in enumerate(stack3[::-1]): index = len(stack3) - i - 1 carry, stack3[index] = divmod(val + carry, 10) if carry and index == 0: stack3 = [1] + stack3 elif carry: stack3[index - 1] += 1 # transfer stack3 to a linkedList result = ListNode(0) c = result for item in stack3: c.next = ListNode(item) c = c.next return result.next

Python 版本的思路与前两者略有不同，采用对齐 + 列表推导的写法：

• 先通过diff = abs(len(stack1) - len(stack2))计算两链表长度差，用[0]*diff + stack对较短的栈高位补零，使两个栈长度一致；
• zip逐位相加得到 stack3（此时 stack3 是高位在前）；
• 从**低位（列表尾部）**反向遍历 stack3，用divmod(val + carry, 10)同时求出进位与当前位，若产生进位则向前一位 +1；若最高位仍有进位，则整体在前面插入[1]；
• 最后把 stack3 依次转为链表节点返回。

解法二：反转链表再相加（经典套路）

除了栈，题解文档还给出了另一条思路：先将两个链表逆置（变为低位在前），按 problems/2.add-two-numbers.md 的普通两数相加逻辑逐位相加，最后把结果再次逆置，恢复高位在前的顺序。

// 逆置，相加，再逆置。跑完所有测试用例比第一种解法少花4ms class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { auto rl1 = reverseList(l1); auto rl2 = reverseList(l2); auto ret = add(rl1, rl2); return reverseList(ret); } private: ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* cur = head; ListNode* next = NULL; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } ListNode* add(ListNode* l1, ListNode* l2) { ListNode* ret = nullptr; ListNode* cur = nullptr; int carry = 0; while (l1 != nullptr || l2 != nullptr || carry != 0) { carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val); auto temp = new ListNode(carry % 10); carry /= 10; if (ret == nullptr) { ret = temp; cur = ret; } else { cur->next = temp; cur = cur->next; } l1 = l1 == nullptr ? nullptr : l1->next; l2 = l2 == nullptr ? nullptr : l2->next; } return ret; } };

这个版本的关键组件：

• reverseList：经典三指针迭代反转，prev / cur / next逐步翻转 next 指针方向，返回值即反转后的新头；
• add：与 problems/2.add-two-numbers.md 中 C++ 解法同构——carry += (l1?l1->val:0) + (l2?l2->val:0)累积进位，carry % 10为当前位、carry /= 10更新进位，while 条件同样包含carry != 0以兜底最高位进位；
• 原题解注释给出实测对比：反转相加再反转的写法比栈解法跑完所有测试用例少花约 4ms，可作为工程上的取舍参考。

不过要注意：反转法修改了输入链表，不满足题目的进阶约束（不能修改输入链表）。如果面试中先给出反转法，面试官追问"输入链表不能修改怎么办"，栈解法就是完美的应对方案——这也正是这道题把两种解法放在一起学习的价值所在。

与 2. 两数相加（Add Two Numbers）的对比

在 problems/2.add-two-numbers.md 中，链表本身就是低位在前的，因此可以直接从头到尾同步遍历、用一个carried/carry变量完成进位，同时配合虚拟头节点简化头指针处理。而 445 题只是把存储顺序反转了，难题就从"怎么加"变成了"怎么在不能回退的单链表上拿到低位"——理解了这一点，两题即可互相迁移。仓库的 SUMMARY.md 也将 0002. 两数相加 与 0445. 两数相加 II 编排在相邻位置，collections/medium.md 的题目清单中同样收录了 0445，二者是天然的对照练习组合。

复杂度分析

设两个链表的长度分别为 M 和 N：

• 时间复杂度：$O(M + N)$。栈解法中，入栈、弹栈、重建链表各遍历一遍节点；反转法中，两次反转加一次相加同样是线性遍历；
• 空间复杂度：$O(M + N)$。栈解法需要两个输入栈与一个结果栈（或结果链表的隐式空间）；反转法虽然迭代反转是 $O(1)$ 额外空间，但整体仍属于线性量级。

实战要点总结

1. 高位在前的链表加法，核心是先逆序访问：栈是"不改输入"的优雅工具，反转是"空间更省"的直接手段，两种都必须会写；
2. 进位处理是 bug 高发区：记住当前位 = (a + b + carry) % 10、进位 = (a + b + carry) / 10，并且循环结束后单独检查残留进位（如 1 + 99 = 100 的最高位 1）；
3. 循环终止条件写成stack.length > 0/!s1.empty() || !s2.empty() || carry != 0，可以省去大量边界判断；
4. 链表重建多用虚拟头（dummy），与 thinkings/linked-list.md 的链表专题技巧一脉相承，可进一步阅读该专题掌握"一个原则、两个考点、三个注意、四个技巧"的完整方法论。

本题完整题解与多语言代码位于 problems/445.add-two-numbers-ii.md，姊妹题见 problems/2.add-two-numbers.md，仓库根目录的 README.md 与 SUMMARY.md 可帮助定位更多链表与栈相关的题解。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode