牛客BM11题：从竖式加法到栈的妙用

引言：从生活场景到算法问题

想象你在小学时做过的竖式加法：把两个数字右对齐，从个位开始逐位相加，遇到进位就向高位传递。当我们需要处理链表表示的大数相加时，这个熟悉的场景突然变得复杂起来——因为链表只能顺序访问，而加法需要从最低位开始处理。这就是BM11题的核心挑战。

一、问题重述与难点分析

给定两个链表，每个节点存储0-9的数字，链表整体代表一个整数（如9->3->7表示937）。要求返回表示两数之和的新链表。关键难点在于：

1. 链表是单向的，无法直接反向访问

2. 数字长度可能不同（如1234+56）

3. 最高位可能产生额外进位（如999+1=1000）

二、核心解法：栈的应用

为什么选择栈？

栈的"后进先出"(LIFO)特性完美解决了链表反向访问的问题：

1. 第一次遍历：将链表节点值压入栈，栈顶即为数字最低位

2. 计算阶段：每次弹出栈顶元素，相当于从个位开始处理

3. 结果构建：使用头插法自然形成正确顺序的结果链表

三、代码实现

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        stack<int> s1, s2;

        // 将链表数据压入栈（反向处理）
        while (head1) {
            s1.push(head1->val);
            head1 = head1->next;
        }
        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()) {
                sum += s1.top();
                s1.pop();
            }
            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }

            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = res;  // 头插法构建结果链表
            res = node;
        }
        return res;
    }
};

四、案例演示

以9->3->7 + 6->3为例：

栈s1: [7,3,9]   (对应937)

栈s2: [3,6]    (对应63)

计算过程：

1. 7+3=10 → 写0进1

2. 3+6+1=10 → 写0进1 

3. 9+0+1=10 → 写0进1

4. 处理最后进位1 → 写1

结果：1->0->0->0 (1000)

五、总结与拓展

通过这个问题，我们学到了：

1. 1.栈结构在反向处理问题中的妙用

2. 2.头插法构建链表的技巧

3. 3.进位处理的标准化模式

掌握这种"数据结构特性转化问题本质"的思维，比记住解法本身更重要。