牛客BM11题解析：链表相加的栈解法
2天前
一、题目解读
牛客BM11题要求实现两个链表的相加操作，即将两个链表对应节点的值相加，并返回相加后的结果链表。题目考察的核心在于如何处理链表的逆序相加与进位问题，需要兼顾数据结构操作与数学逻辑的结合。
二、解题思路
采用“栈+逆序处理”策略，巧妙避开链表顺序遍历的麻烦。思路如下：
1. 逆序存储：利用栈的先进后出特性，将两个链表元素分别压入栈s1和s2，实现链表元素的逆序访问（从尾到头）。
2. 同步相加：通过循环遍历栈顶元素，模拟手动加法过程：逐位相加、处理进位（carry）、构建新节点。
3. 头插法构建结果：每次将新节点插入到结果链表头部（head），确保最终结果链表顺序正确。
三、解题步骤
1. 初始化栈与变量：创建两个栈s1、s2，用于存储链表元素；定义carry（进位）与结果链表头节点res。
2. 逆序压栈：通过循环遍历head1、head2，将节点值依次压入栈，实现链表元素的逆序存储。
3. 栈顶元素相加：
循环条件：任一栈非空或存在进位（carry>0）。
计算当前位和sum：取两栈顶元素（若栈空则忽略）+ 进位。
更新进位：sum/10，取整数部分。
构建新节点：sum%10（取余数），头插法插入res链表。
4. 返回结果链表：最终res即为相加后的正确顺序链表。
四、代码与注释
class Solution {
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
stack<int> s1, s2; // 创建栈存储逆序链表元素
// 将链表1逆序压栈
while (head1) {
s1.push(head1->val);
head1 = head1->next;
}
// 将链表2逆序压栈
while (head2) {
s2.push(head2->val);
head2 = head2->next;
}
int carry = 0; // 进位标志
ListNode* res = nullptr; // 结果链表头节点
// 从低位到高位逐位相加
while (!s1.empty() ||!s2.empty() || carry) {
int sum = carry; // 当前位和初始值为进位
if (!s1.empty()) { // 若栈1不空，加入当前元素
sum += s1.top();
s1.pop();
}
if (!s2.empty()) { // 若栈2不空，加入当前元素
sum += s2.top();
s2.pop();
}
carry = sum / 10; // 更新进位
ListNode* node = new ListNode(sum % 10); // 创建新节点（取余数）
node->next = res; // 头插法插入节点
res = node;
}
return res;
}
};五、总结
本解法通过栈的逆序处理，将链表相加转化为简单的栈顶元素逐位相加问题，避免了复杂的指针操作与递归。核心优势在于：
● 时间复杂度O(max(n,m))：n、m为两链表长度，仅需一次遍历+栈操作。
● 空间复杂度O(n+m)：栈存储链表元素。
● 代码简洁性：头插法直接构建结果链表，无需额外反转或调整顺序。
该思路适用于链表中“从尾到头”操作的通用场景，是解决此类问题的经典方法。
原创内容 转载请注明出处
