牛客BM11题解析：链表相加的栈解法

一、题目解读

牛客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)：栈存储链表元素。

● 代码简洁性：头插法直接构建结果链表，无需额外反转或调整顺序。

该思路适用于链表中“从尾到头”操作的通用场景，是解决此类问题的经典方法。