链表表示数字相加：正序存储的挑战与解决方案-java教程-PHP中文网

链表表示数字相加：正序存储的挑战与解决方案

本文深入探讨了如何将两个以正序链表形式存储的非负整数相加，并返回其和。由于标准加法从低位开始，而链表从高位开始，这带来了对齐和进位处理的挑战。文章将分析常见错误，并提供两种高效的解决方案：链表反转法和栈辅助法，并附带详细代码示例。

引言：正序链表数字相加的难题

在编程挑战中，我们经常会遇到使用链表来表示大整数的问题。本教程将聚焦于一个特定场景：给定两个非空的单向链表，每个链表代表一个非负整数，其中数字的各位是按正序（即最高位在前）存储的。我们的目标是将这两个数字相加，并以一个新的链表形式返回它们的和。

例如：输入：l1 = [2,4,3] (表示数字 243)，l2 = [5,6,4] (表示数字 564) 输出：[8,0,7] (表示数字 807) 解释：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
        // head.val = generateSumList(l1.next, l2.next, head.next); 
        // 实际上，问题出在generateSumList的res参数传递上
        return head; // 最终返回的head可能不正确
    }

    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        int rest, sum;

        // ... 忽略了处理l1或l2为空的情况，这在实际递归中会更复杂

        // 核心问题之一：如果res在某个递归层级是null，这里会抛出NPE
        // 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;
        // }
        return 0; // 占位符
    }
}

登录后复制

上述尝试的递归方法存在两个主要问题：

空指针异常 (NullPointerException, NPE)：当 addTwoNumbers 函数调用 generateSumList(l1.next, l2.next, head.next) 时，head 是一个新创建的 ListNode(0)，其 next 成员默认是 null。这意味着 generateSumList 的 res 参数在某些递归调用中可能会接收到 null。当 res 为 null 时，如果代码尝试访问 res.next 或 res.val，就会导致 NullPointerException。例如，在 rest = generateSumList(l1.next, l2.next, res.next); 这行代码中，如果 res 是 null，res.next 就会引发 NPE。
逻辑错误：位数对齐问题：该递归方法试图从链表的头部（最高位）开始同步遍历 l1 和 l2。这对于加法运算是错误的。例如，如果 l1 = [1,2] (12) 和 l2 = [3,4,5] (345)，期望的结果是 [3,5,7] (357)。如果从左到右同步处理：
- 第一次递归可能处理 1 和 3。
- 第二次递归可能处理 2 和 4。
- 5 最终会被单独处理。这种处理方式完全没有考虑数字的实际位值。数字加法必须将个位与个位相加，十位与十位相加，依此类推。由于链表是正序存储，链表头部是最高位，尾部是最低位。在不等长的链表情况下，简单地同步遍历无法保证正确对齐，导致结果错误。

为了正确解决这个问题，我们需要找到一种方法，能够从链表的尾部（最低位）开始进行加法，或者以某种方式模拟这种行为。

解决方案一：链表反转法

链表反转法是一种直观且常用的解决方案。其核心思想是，既然正序存储的链表不便于从低位开始相加，我们可以先将它们反转，使其变为逆序存储（低位在前），然后执行标准的链表数字相加操作，最后再将结果链表反转回来。

核心思想：

将输入的两个链表 l1 和 l2 反转。
对反转后的链表执行传统的链表数字相加（类似于 LeetCode 2. Add Two Numbers 问题，其中数字是逆序存储的）。
将相加得到的结果链表再次反转，以恢复正序。

步骤详解：

实现链表反转函数 reverseList(ListNode head)：这个辅助函数用于将任何给定的链表反转。

public 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 最终指向原链表的尾部，即新链表的头部
}

登录后复制

主函数 addTwoNumbers(ListNode l1, ListNode l2) 实现：

爱图表

AI驱动的智能化图表创作平台

查看详情

反转输入链表：

ListNode reversedL1 = reverseList(l1);
ListNode reversedL2 = reverseList(l2);

登录后复制

执行加法操作：创建一个哑节点 (dummy head) 来简化结果链表的构建。遍历 reversedL1 和 reversedL2，逐位相加，并处理进位。

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;
}
// 此时 dummyHead.next 是逆序的结果链表

登录后复制

反转结果链表：将通过加法得到的逆序结果链表再次反转，得到最终的正序结果。
```
return reverseList(dummyHead.next);
```
登录后复制

完整示例代码：

import java.util.Stack;

class Solution {

    // Definition for singly-linked list.
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 辅助函数：反转链表
     * @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;
            curr = nextTemp;
        }
        return prev;
    }

    /**
     * 方案一：链表反转法
     * 将正序存储的链表数字相加
     * @param l1 第一个数字链表
     * @param l2 第二个数字链表
     * @return 和的链表
     */
    public ListNode addTwoNumbersByReversing(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);
    }
}

登录后复制

复杂度分析：

时间复杂度：O(N + M)，其中 N 和 M 分别是两个输入链表的长度。反转操作需要 O(N) 和 O(M)，加法操作需要 O(max(N, M))，最后反转结果链表需要 O(max(N, M))。总体为线性时间复杂度。
空间复杂度：O(N + M)，用于存储反转后的链表（虽然是原地反转，但新的结果链表需要 O(max(N, M)) 空间）。

解决方案二：栈辅助法

栈辅助法是另一种有效的解决策略，它避免了链表的多次反转操作，而是利用栈的 LIFO (后进先出) 特性来模拟从低位到高位的访问顺序。

核心思想：

将两个输入链表的所有数字分别压入两个栈中。这样，栈顶元素就代表着链表的尾部（即数字的最低位）。
从两个栈中逐个弹出数字进行相加，同时处理进位。
将相加的结果数字构建成一个新的链表。由于是从低位向高位构建，新的节点需要通过“头插法”添加到结果链表的头部。

步骤详解：

将链表数字压入栈中：遍历 l1 和 l2，将其 val 值依次压入 stack1 和 stack2。

Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();

while (l1 != null) {
    stack1.push(l1.val);
    l1 = l1.next;
}
while (l2 != null) {
    stack2.push(l2.val);
    l2 = l2.next;
}

登录后复制

执行加法操作并构建结果链表：初始化一个进位 carry = 0。循环，直到两个栈都为空且 carry 为 0。在循环中：

从栈顶弹出数字（如果栈不为空），否则取 0。
计算当前位的和 sum = val1 + val2 + carry。
更新进位 carry = sum / 10。
创建新的 ListNode，其值为 sum % 10。
将新节点通过头插法添加到结果链表的头部。

ListNode resultHead = null; // 结果链表的头节点
int carry = 0;

while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
    int val1 = !stack1.isEmpty() ? stack1.pop() : 0;
    int val2 = !stack2.isEmpty() ? stack2.pop() : 0;

    int sum = val1 + val2 + carry;
    carry = sum / 10;
    int digit = sum % 10;

    ListNode newNode = new ListNode(digit);
    newNode.next = resultHead; // 头插法
    resultHead = newNode;
}

登录后复制

返回结果链表：最终 resultHead 就是正序的结果链表的头部。

完整示例代码：

import java.util.Stack;

class Solution {

    // Definition for singly-linked list.
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 方案二：栈辅助法
     * 将正序存储的链表数字相加
     * @param l1 第一个数字链表
     * @param l2 第二个数字链表
     * @return 和的链表
     */
    public ListNode addTwoNumbersByStacks(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2

登录后复制

以上就是链表表示数字相加：正序存储的挑战与解决方案的详细内容，更多请关注php中文网其它相关文章！