链表相加实现方法全解析

本文深入解析了链表正向存储数字相加的实现方法，这是一种常见的算法面试题。与逆向存储不同，正向存储增加了计算难度。文章首先剖析了常见错误，例如空指针异常和位数不对齐等逻辑问题。随后，详细介绍了两种主流解决方案：**反转链表法**和**栈辅助法**。反转链表法通过先反转链表，再进行逆向相加，最后再次反转得到结果，是推荐的解法。而栈辅助法利用栈的后进先出特性，无需反转链表也能实现相加。文章提供了完整的Java代码示例，并分析了两种方法的复杂度，同时强调了进位处理、链表长度不一致等关键注意事项，旨在帮助读者彻底掌握链表相加的技巧，提升算法能力。

本教程旨在解决如何在链表正向存储数字（最高位在前）的情况下实现两数相加。由于数字的正向存储使得直接逐位相加变得复杂，文章将首先分析常见错误，然后详细介绍两种主流的解决方案：通过反转链表将问题转化为逆向存储相加，以及利用栈结构辅助实现，并提供完整的Java代码示例与注意事项。

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 可能并不代表数字的相同位数（例如，一个是个位，一个是十位），从而导致结果错误。

例如，[2,4,3] (243) 和 [5,6,4,8] (5648)，如果直接从头递归，2 和 5 相加，这显然是错误的，因为它们分别代表百位和千位。我们需要的是 3 和 8 相加，4 和 4 相加，等等。

3. 解决方案：反转链表法 (推荐)

解决正向存储链表相加最直观且常用的方法是：首先将两个输入链表反转，使其变为逆向存储（个位在前），然后按照经典的逆向存储链表相加方法处理，最后再将结果链表反转回正向。

3.1 步骤概览

1. 反转输入链表： 将 l1 和 l2 分别反转。
2. 相加反转后的链表： 迭代遍历反转后的链表，逐位相加，处理进位，构建一个新的结果链表。这个结果链表也是逆向存储的。
3. 反转结果链表： 将第二步得到的结果链表再次反转，使其变为正向存储，这就是最终答案。

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 步骤概览

1. 入栈： 遍历两个输入链表，将其所有数字依次压入两个独立的栈中。这样，栈顶元素就是链表的最后一个数字（即个位）。
2. 出栈相加： 从两个栈中同时弹出数字，进行相加并处理进位。将相加结果的新节点连接到结果链表的头部（因为我们是从个位向高位构建）。
3. 返回结果： 最终构建出的链表就是正向存储的和。

4.2 主函数：实现两数相加 (使用栈)

import java.util.Stack;

public class Solution {
    // ListNode 定义如上所示

    public ListNode addTwoNumbersWithStacks(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> 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) 的额外空间来存储栈。
  • 对于面试或实际应用，两者都是可接受的解决方案。

通过以上两种方法，我们可以有效地解决在正向存储数字的链表中实现两数相加的问题，避免了直接操作正向链表带来的复杂性。理解并掌握这些技巧对于处理链表相关的复杂问题至关重要。

本篇关于《链表相加实现方法全解析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！