引言：正序链表数字相加问题
在计算机科学中，链表常用于表示任意长度的数字，尤其是在处理大数运算时。本问题要求我们将两个非空的链表所代表的非负整数进行相加，并将它们的和以一个新的链表形式返回。关键在于，这些数字的位数是正序存储的，即链表的头部代表数字的最高位。每个节点包含一个单位数字。
示例： 假设链表 l1 代表数字 243，l2 代表数字 564。
l1: 2 --> 4 --> 3 l2: 5 --> 6 --> 4 结果: 8 --> 0 --> 7 (因为 243 + 564 = 807)
其中，链表节点 ListNode 的定义如下：
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}剖析常见误区：递归解法中的陷阱
在尝试解决此类问题时，初学者可能会尝试使用递归方法。然而，对于正序存储的链表数字相加，直接的递归往往会遇到挑战，甚至导致运行时错误。我们来分析一个典型的错误递归实现及其原因。
考虑以下递归尝试：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0); // 创建一个虚拟头节点
// 尝试通过递归生成和链表，并将结果赋值给head.val，但head.next是null
head.val = generateSumList(l1.next, l2.next, head.next); // 这里将null传递给res
return head; // 返回的head可能只包含一个val，且next仍为null
}
public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
int rest, sum;
// ... 省略了处理不等长链表的错误逻辑 ...
// 核心递归逻辑：
// 假设 l1, l2, res 都不为 null
rest = generateSumList(l1.next, l2.next, res.next); // 尝试递归处理后续节点，并获取进位
sum = l1.val + l2.val + rest; // 计算当前位的和
if (sum > 9) {
res.val = sum % 10;
return 1; // 返回进位
} else {
res.val = sum;
return 0; // 返回进位
}
}
}1. 空指针异常（NPE）分析： 该递归方案最直接的问题是 NullPointerException。在 addTwoNumbers 方法中，创建了一个 ListNode head = new ListNode(0);。此时，head.next 默认是 null。当调用 generateSumList(l1.next, l2.next, head.next) 时，第三个参数 res 接收到的就是 null。
如果 l1.next 和 l2.next 都不为 null（即链表长度足够），程序会进入 generateSumList 的主递归体，并执行 rest = generateSumList(l1.next, l2.next, res.next);。由于此时 res 是 null，尝试访问 res.next 就会导致 java.lang.NullPointerException。
2. 核心逻辑缺陷：正序加法的位对齐问题 即使解决了 NPE 问题，该递归方法的核心逻辑也存在根本性缺陷：
- 加法顺序与链表顺序不匹配： 数字加法是从最低位（个位）开始，向最高位（左侧）传播进位。然而，正序链表将最高位放在链表头部，最低位在尾部。直接从头部开始递归，然后尝试在返回时处理进位，会导致数字位错位。
- 不等长链表处理困难： 当两个链表长度不一致时，例如 l1 = [1,2,3] 和 l2 = [4,5]，如果从头部开始匹配，l1.val=1 会与 l2.val=4 相加。但实际运算中，1 是百位，4 是十位，它们不应该直接相加。正确的做法是 3 与 5 相加，2 与 4 相加，最后 1 单独处理。该递归方案未能有效解决这种位对齐问题。
因此，对于正序链表数字相加，我们需要一种机制来逆序访问链表中的数字，或者预先处理使其能够从低位开始相加。
正确解法一：基于栈的实现 (推荐)
解决正序链表数字相加问题的有效方法是利用栈（Stack）。栈的“后进先出”（LIFO）特性可以帮助我们模拟从链表尾部（即数字的最低位）开始访问数字，从而实现正确的加法逻辑。
核心思想：
- 将两个链表的所有数字分别压入两个栈中。这样，栈顶元素就代表了数字的最低位。
- 从栈顶开始弹出数字并相加，同时处理进位。
- 构建结果链表时，将计算出的当前位数字作为新节点，并将其插入到当前结果链表的头部。这样，结果链表自然就是正序的。
实现步骤：
-
压栈：
- 遍历第一个链表 l1，将其每个节点的值依次压入 s1 栈。
- 遍历第二个链表 l2，将其每个节点的值依次压入 s2
