链表实现大数相加技巧与误区

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《链表实现大整数加法：技巧与常见错误》，本文主要会讲到等等知识点，希望大家一起学习进步，也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧！

引言：链表表示大整数加法

在计算机科学中，链表常用于表示长度不定的数据结构，包括大整数。当每个节点存储一个数字时，链表可以有效地表示一个非常大的整数。本教程将解决一个特定问题：给定两个非空的链表，它们代表两个非负整数，其中数字是正向存储的（即最高位在链表头部），每个节点包含一个单一数字。目标是将这两个数字相加，并将结果以一个新的链表形式返回。

例如： 输入：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; }
}

正向链表求和的挑战

直接处理正向存储的链表进行加法运算存在固有挑战。传统的数字加法是从最低位（个位）开始，逐位相加并处理进位。然而，在正向链表中，最低位位于链表的末尾。

1. 无法直接对齐最低位： 如果两个链表长度不同，我们无法直接从头部开始遍历并相加，因为当前节点的数字可能代表不同的位数（例如，[1,2,3] 和 [4,5]，1 和 4 都是最高位，但它们分别代表百位和十位，不能直接相加）。
2. 进位处理： 加法运算中产生的进位需要向前一位传递。如果从链表头部开始处理，进位需要向已经处理过的更高位传递，这与链表的单向性相悖，因为链表只能向前遍历。

因此，解决这个问题的关键在于找到一种方法，能够从链表的末尾（即最低位）开始处理数字，或者以某种方式逆向处理进位。

解决方案一：反转链表再求和（推荐）

这是解决正向链表求和问题最直观且常用的方法之一。其核心思想是：将正向链表反转为逆向链表（最低位在前），然后按照处理逆向链表加法的经典方法进行求和，最后再将结果链表反转回正向。

核心步骤：

1. 反转链表: 实现一个辅助函数，将给定的链表反转。
2. 逆序链表相加: 实现一个函数，对两个已反转的链表执行加法运算。这个过程与经典的“两数相加”（LeetCode 2）问题相同，即从头开始遍历，逐位相加并处理进位，构建一个新的结果链表。
3. 反转结果链表: 将步骤2中得到的逆序结果链表再次反转，以得到最终的正向结果。

示例代码 (Java):

import java.util.Stack; // 也可以不用Stack，纯链表操作

public class Solution {

    /**
     * 反转链表辅助函数
     * @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 最终是原链表的尾节点，也就是反转后的头节点
    }

    /**
     * 对两个正向存储数字的链表进行求和
     * @param l1 第一个链表
     * @param l2 第二个链表
     * @return 求和结果链表 (正向存储)
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 步骤 1: 反转两个输入链表
        ListNode l1Reversed = reverseList(l1);
        ListNode l2Reversed = reverseList(l2);

        // 步骤 2: 对反转后的链表进行求和 (经典逆序链表加法)
        ListNode dummyHead = new ListNode(0); // 虚拟头节点，方便处理
        ListNode current = dummyHead;
        int carry = 0; // 进位

        while (l1Reversed != null || l2Reversed != null || carry != 0) {
            int x = (l1Reversed != null) ? l1Reversed.val : 0;
            int y = (l2Reversed != null) ? l2Reversed.val : 0;

            int sum = x + y + carry;
            carry = sum / 10;           // 计算新进位
            current.next = new ListNode(sum % 10); // 创建新节点存储当前位数字
            current = current.next;     // 移动到下一个节点

            if (l1Reversed != null) l1Reversed = l1Reversed.next;
            if (l2Reversed != null) l2Reversed = l2Reversed.next;
        }

        // 步骤 3: 反转求和结果链表，得到最终正向结果
        return reverseList(dummyHead.next);
    }
}

复杂度分析：

• 时间复杂度: 反转两个链表各需要 O(N) 和 O(M) 时间，其中 N 和 M 分别是两个链表的长度。求和过程需要 O(max(N, M)) 时间。最后反转结果链表需要 O(max(N, M)) 时间。因此，总时间复杂度为 O(N + M)。
• 空间复杂度: 反转链表通常是原地操作，不需要额外空间（O(1)）。但如果 reverseList 的实现不是原地反转，则可能需要 O(N) 空间。求和过程中创建了新的结果链表，其长度最多为 max(N, M) + 1，因此空间复杂度为 O(max(N, M))。

解决方案二：利用栈或递归（无需显式反转）

除了反转链表，我们还可以利用栈的“后进先出”特性，或者递归的调用栈，来模拟从链表末尾（最低位）开始处理数字。

1. 利用栈的方法：

1. 压栈: 将两个链表的所有数字分别压入两个栈中。这样，栈顶元素就代表了链表的最低位。
2. 出栈求和: 从两个栈中同时弹出数字进行相加，并处理进位。
3. 构建结果链表: 将每次相加的结果（当前位数字）作为新节点，并将其插入到结果链表的头部。由于我们是从最低位开始构建，将新节点插入头部能够自然地形成正向的结果链表。

示例代码 (Java - 栈方法):

import java.util.Stack;

public class SolutionStack {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        // 将链表l1的数字压入s1
        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        // 将链表l2的数字压入s2
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

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

        // 从栈中弹出数字进行相加，直到两个栈都为空且没有进位
        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int x = s1.isEmpty() ? 0 : s1.pop();
            int y = s2.isEmpty() ? 0 : s2.pop();

            int sum = x + y + carry;
            carry = sum / 10;

            // 将当前位数字作为新节点插入到结果链表的头部
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = head; // 新节点指向当前头节点
            head = newNode;      // 更新头节点为新节点
        }
        return head;
    }
}

复杂度分析：

• 时间复杂度: 遍历两个链表并压栈需要 O(N + M) 时间。从栈中弹出并构建结果链表需要 O(max(N, M)) 时间。总时间复杂度为 O(N + M)。
• 空间复杂度: 两个栈最多存储 N 和 M 个数字，结果链表最多存储 max(N, M) + 1 个数字。因此，总空间复杂度为 O(N + M)。

原递归尝试的分析与修正

原始问题中提供了一个递归尝试，但它存在 NullPointerException 和逻辑错误。

NullPointerException 诊断：

原始代码片段：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0); // head.next 默认为 null
        head.val = generateSumList(l1.next, l2.next, head.next); // 传入 head.next (null)
        return head;
    }

    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        // ...
        rest = generateSumList(l1.next, l2.next, res.next); // 当 res 为 null 时，res.next 会导致 NPE
        // ...
    }
}

问题出在 addTwoNumbers 方法中，head 节点的 next 成员默认是 null。当 generateSumList 被调用时，head.next (即 null) 被作为 res 参数传入。在 generateSumList 内部，如果 l1.next 和 l2.next 都不为 null，它会尝试执行 res.next，此时 res 是 null，因此会抛出 NullPointerException。

逻辑错误分析：

原始递归方法的主要逻辑缺陷在于它没有正确处理不等长链表的对齐问题。虽然它试图通过递归到达链表末尾，但 sum = l1.val + l2.val + rest; 这行代码在递归回溯时，会简单地将当前 l1.val 和 l2.val 相加。如果链表长度不同，这些 l1.val 和 l2.val 并不代表相同的位数。例如，[1,2,3] 和 [4,5]，在递归到 1 和 4 时，它们是各自链表的第一个元素，但实际分别代表百位和十位，直接相加是错误的。正确的做法是，必须从最低位（个位）开始相加，并逐级处理进位。

正确的递归思路（简述）： 如果坚持使用递归，需要更复杂的策略：

1. 对齐链表: 先遍历两个链表，获取它们的长度。如果长度不同，在较短链表的头部“填充”逻辑上的零，使其与较长链表等长。
2. 深度优先递归: 递归函数从链表头部开始，一直递归到链表的末尾（即最低位）。
3. 回溯计算: 在递归回溯时，从最低位开始执行加法，并向上层返回进位。
4. 构建结果: 在回溯过程中，根据计算结果创建新的节点，并将其链接起来。这种方法通常需要一个额外的函数来处理进位，并在构建结果链表时将新节点插入到当前链表的头部。这种方法比栈或反转方法更复杂，容易出错。

注意事项

• 进位处理: 无论哪种方法，都必须正确处理进位。当两个数字和进位相加大于等于 10 时，需要将和除以 10 的结果作为进位传递给下一位，将和对 10 取模的结果作为当前位数字。
• 最终进位: 如果在所有数字相加完毕后，仍然存在进位（例如 99 + 1 = 100），则需要在结果链表的最高位添加一个新的节点来存储这个进位。
• 不同长度链表: 两种解决方案都通过填充零（隐式或显式）或循环条件 (s1.isEmpty() || s2.isEmpty() || carry != 0) 来优雅地处理不同长度的链表。
• 数字 0 的特殊情况: 如果输入链表代表数字 0，即 [0]，它应该被正确处理。上述解决方案都能正确处理这种情况。

总结

处理链表表示的正向大整数加法，其核心挑战在于数字的“正向”存储与传统加法“从低位到高位”的矛盾。为了克服这一挑战，我们必须将问题转化为从链表末尾（最低位）开始处理。

• 反转链表再求和是一种高效且易于理解的策略，它将问题分解为经典的逆序链表加法。
• 利用栈是另一种无需显式反转链表的方法，它通过栈的LIFO特性自然地实现了从低位到高位的处理顺序。

这两种方法都能提供健壮的解决方案，而原始的递归尝试则因其对齐逻辑和进位处理的复杂性而容易导致错误。在实际开发中，应根据具体情况选择最适合的实现方式，通常“反转链表”或“利用栈”是更推荐的选择。

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