1. 理解问题：正向存储的链表相加
给定两个非空链表，它们分别代表两个非负整数。每个链表节点包含一个数字，并且数字是正向存储的（即最高位在链表头部）。我们的目标是将这两个数字相加，并以同样的正向存储链表形式返回它们的和。
例如： 输入：l1 = [2,4,3] (表示数字 243)，l2 = [5,6,4] (表示数字 564) 输出：[8,0,7] (表示数字 807) 解释：243 + 564 = 807
链表节点定义如下：
// Definition for singly-linked list.
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; }
}与经典的“逆向存储链表相加”问题（如LeetCode 2）不同，正向存储要求我们从链表的末尾（即数字的个位）开始相加，而链表的单向特性使得直接访问末尾非常不便。
2. 分析原始尝试及错误
原始尝试使用递归方法，试图从链表末尾开始处理，这本身是解决正向存储问题的一种思路，但实现上存在关键错误。
2.1 运行时错误：NullPointerException (NPE)
原始代码中的 addTwoNumbers 方法初始化 head 节点，并将其 next 成员（此时为 null）作为 res 参数传递给 generateSumList。
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0); // head.next 默认为 null
// ...
// 调用 generateSumList 时，head.next (null) 被赋给 res
head.val = generateSumList(l1.next, l2.next, head.next);
return head;
}
public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
// ...
// 当 l1.next 和 l2.next 都不为 null 时，会执行以下语句：
rest = generateSumList(l1.next, l2.next, res.next);
// 此时 res 可能是 null，导致 res.next 触发 NullPointerException
// ...
}
}当 res 参数为 null 时，尝试访问 res.next 就会导致 NullPointerException。在原始代码中，addTwoNumbers 方法将 head.next（初始为 null）传递给 generateSumList 的 res 参数，如果递归调用链中 res 保持 null 且尝试访问 res.next，就会抛出此异常。
2.2 逻辑错误：数字位不对齐
即使解决了 NPE，原始的递归方法也无法正确处理不等长的链表。对于正向存储的数字，我们需要将它们的个位对齐，十位对齐，以此类推。原始代码的递归逻辑并没有显式地处理链表长度不一致的情况，导致在 sum = l1.val + l2.val + rest; 这一步，相加的 l1.val 和 l2.val 可能并不代表数字的相同位数（例如，一个是个位，一个是十位），从而导致结果错误。
Metafox 是一个企业内容管理系统，使用一个特别的模板系统，你可通过一些特定的设计和代码来轻松创建 Web 网站，内容存储在 SQL 关系数据库，通过 Web 进行管理，简单、快速而且高效。 Metafox 0.9.1 发布，该版本改用一种更棒的 URL 风格，实现了 RSS 源（可包含远端网站内容到 Metafox 段中），重定向老的访问密钥到新的密钥，增加 RotateAntispam 技
例如，[2,4,3] (243) 和 [5,6,4,8] (5648)，如果直接从头递归，2 和 5 相加，这显然是错误的，因为它们分别代表百位和千位。我们需要的是 3 和 8 相加，4 和 4 相加，等等。
3. 解决方案：反转链表法 (推荐)
解决正向存储链表相加最直观且常用的方法是：首先将两个输入链表反转，使其变为逆向存储（个位在前），然后按照经典的逆向存储链表相加方法处理，最后再将结果链表反转回正向。
3.1 步骤概览
- 反转输入链表： 将 l1 和 l2 分别反转。
- 相加反转后的链表： 迭代遍历反转后的链表，逐位相加，处理进位，构建一个新的结果链表。这个结果链表也是逆向存储的。
- 反转结果链表： 将第二步得到的结果链表再次反转，使其变为正向存储，这就是最终答案。
3.2 辅助函数：反转链表
我们需要一个通用的函数来反转链表。
/**
* 反转单链表
* @param head 链表头节点
* @return 反转后的链表头节点
*/
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 暂存下一个节点
curr.next = prev; // 当前节点指向前一个节点
prev = curr; // prev 向前移动
curr = nextTemp; // curr 向前移动
}
return prev; // prev 最终指向原链表的尾部，即反转后的头部
}3.3 主函数：实现两数相加
public class Solution {
// ListNode 定义如上所示
public ListNode addTwoNumbersForwardOrder(ListNode l1, ListNode l2) {
// 1. 反转输入链表
ListNode reversedL1 = reverseList(l1);
ListNode reversedL2 = reverseList(l2);
// 2. 相加反转后的链表（经典逆向相加问题）
ListNode dummyHead = new ListNode(0); // 哨兵节点，简化结果链表的构建
ListNode current = dummyHead;
int carry = 0; // 进位
while (reversedL1 != null || reversedL2 != null || carry != 0) {
int val1 = (reversedL1 != null) ? reversedL1.val : 0;
int val2 = (reversedL2 != null) ? reversedL2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10; // 计算新的进位
int digit = sum % 10; // 当前位的数字
current.next = new ListNode(digit); // 创建新节点并连接
current = current.next;
if (reversedL1 != null) {
reversedL1 = reversedL1.next;
}
if (reversedL2 != null) {
reversedL2 = reversedL2.next;
}
}
// 3. 反转结果链表
return reverseList(dummyHead.next); // dummyHead.next 是逆向结果链表的头部
}
/**
* 反转单链表 (同上，为完整性再次提供)
*/
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}3.4 复杂度分析
- 时间复杂度： 反转两个链表需要 O(N+M) 时间，其中 N 和 M 分别是两个链表的长度。相加过程需要 O(max(N, M)) 时间。最后反转结果链表需要 O(max(N, M)) 时间。因此，总时间复杂度为 O(N+M)。
- 空间复杂度： 反转操作是原地进行的，不需要额外空间（除了几个指针）。相加过程创建了一个新的结果链表，其长度最多为 max(N, M) + 1。因此，总空间复杂度为 O(max(N, M))。
4. 替代方案：使用栈
另一种不需显式反转链表的方法是利用栈（Stack）的特性。栈是后进先出（LIFO）的数据结构，非常适合处理需要从末尾（个位）开始访问的数据。
4.1 步骤概览
- 入栈： 遍历两个输入链表，将其所有数字依次压入两个独立的栈中。这样，栈顶元素就是链表的最后一个数字（即个位）。
- 出栈相加： 从两个栈中同时弹出数字，进行相加并处理进位。将相加结果的新节点连接到结果链表的头部（因为我们是从个位向高位构建）。
- 返回结果： 最终构建出的链表就是正向存储的和。
4.2 主函数：实现两数相加 (使用栈)
import java.util.Stack;
public class Solution {
// ListNode 定义如上所示
public ListNode addTwoNumbersWithStacks(ListNode l1, ListNode l2) {
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
// 1. 将链表数字压入栈中
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
ListNode head = null; // 结果链表的头部
int carry = 0; // 进位
// 2. 从栈中弹出数字并相加
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int val1 = stack1.isEmpty() ? 0 : stack1.pop();
int val2 = stack2.isEmpty() ? 0 : stack2.pop();
int sum = val1 + val2 + carry;
carry = sum / 10;
int digit = sum % 10;
// 构建结果链表：新节点总是添加到当前链表的头部
ListNode newNode = new ListNode(digit);
newNode.next = head; // 将新节点指向当前的头部
head = newNode; // 更新头部为新节点
}
return head;
}
} 4.3 复杂度分析
- 时间复杂度： 遍历两个链表并压入栈中需要 O(N+M) 时间。从栈中弹出并相加需要 O(max(N, M)) 时间。因此，总时间复杂度为 O(N+M)。
- 空间复杂度： 两个栈分别存储链表中的所有数字，因此需要 O(N+M) 的额外空间。
5. 注意事项与总结
- 进位处理： 无论是哪种方法，都必须正确处理进位。当两个数字相加以及加上进位后大于等于 10 时，需要将进位传递给下一位。同时，如果所有位都相加完毕后仍有进位（例如 99 + 1 = 100），则需要在结果链表的最高位添加一个新节点。
- 链表长度不一： 两种方法都能自然地处理链表长度不一的情况。反转链表法通过在相加阶段检查 null 来补零；栈方法通过检查栈是否为空来补零。
- 哨兵节点 (Dummy Head)： 在构建结果链表时，使用一个哨兵节点（dummyHead）可以大大简化代码，避免对头节点进行特殊判断。
-
选择哪种方法：
- 反转链表法 在空间复杂度上通常更优，因为它只需要常数额外空间用于指针操作（如果反转是原地进行的话），但需要两次遍历和两次反转。
- 栈方法 在代码实现上可能更简洁直观，但需要 O(N+M) 的额外空间来存储栈。
- 对于面试或实际应用，两者都是可接受的解决方案。
通过以上两种方法，我们可以有效地解决在正向存储数字的链表中实现两数相加的问题，避免了直接操作正向链表带来的复杂性。理解并掌握这些技巧对于处理链表相关的复杂问题至关重要。
