Sign in Subscribe
算法

两数相加

loser

• 6 min read
Share

给你两个非空的链表 l1 和 l2，表示两个非负整数。

它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807。

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

模拟加法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        int carry = 0;

        while (l1 != nullptr || l2 != nullptr || carry != 0)
        {
            int sum = carry;

            if (l1 != nullptr)
            {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2 != nullptr)
            {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }

        return dummy.next;
    }
};

核心思想

这题本质上是在链表上模拟竖式加法。

普通加法是从个位开始加，然后把进位传给下一位。

题目中的链表刚好是逆序存储：

[2,4,3] 表示 342

链表头节点就是个位，后面依次是十位、百位。

所以我们可以直接从两个链表头开始，同时向后遍历。

每一轮计算：

  • 当前位来自 l1 的数字
  • 当前位来自 l2 的数字
  • 上一位产生的进位 carry

三者相加后：

  • 当前节点值是 sum % 10
  • 新的进位是 sum / 10

这题最关键的观察是：

因为链表是逆序存储，所以从链表头到链表尾的遍历顺序，正好就是加法从低位到高位的计算顺序。

为什么不能先转成整数再相加

链表长度最多是 100。

这意味着链表表示的数字可能有 100 位。

普通的 int、long long 都无法保存这么大的数字。

所以不能把链表转成整数后相加。

正确做法是逐位处理，和手算加法一样，只保留当前位和进位。

虚拟头节点的作用

代码中使用：

ListNode dummy(0);
ListNode* tail = &dummy;

dummy 是虚拟头节点，不属于最终答案。

它的作用是统一处理结果链表的头节点和后续节点。

每算出一位，就创建一个新节点接到 tail 后面：

tail->next = new ListNode(sum % 10);
tail = tail->next;

最后返回：

dummy.next

就是真正的结果链表头节点。

进位如何处理

每一位相加时，先把上一位的进位加入：

int sum = carry;

然后再加上两个链表当前节点的值。

如果当前和是 sum，那么：

  • 当前位数字是 sum % 10
  • 进位是 sum / 10

例如：

9 + 9 + 1 = 19

当前位应该写 9，进位为 1。

所以：

carry = sum / 10;
tail->next = new ListNode(sum % 10);

循环条件中必须包含：

carry != 0

因为两个链表都遍历完以后，可能还有最后一个进位。

例如：

999 + 1 = 1000

最后需要额外创建一个值为 1 的节点。

链表长度不同怎么办

两个链表长度可能不同。

例如：

l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]

当较短链表已经遍历完时，就把它当前位看作 0。

代码中通过判断空指针处理：

if (l1 != nullptr)
{
    sum += l1->val;
    l1 = l1->next;
}

l2 同理。

只要任意一个链表还没结束，或者还有进位，就继续计算。

完整循环条件是：

while (l1 != nullptr || l2 != nullptr || carry != 0)

边界情况

如果两个链表都是：

[0]

第一轮计算得到：

sum = 0
carry = 0

创建一个值为 0 的节点，返回 [0]。

如果最后一位相加后仍有进位，例如：

[5] + [5]

第一轮生成节点 0，并产生进位 1。

由于 carry != 0，循环继续，生成节点 1。

结果就是：

[0,1]

表示数字 10。

正确性证明

我们证明：算法返回的链表正确表示两个输入数字之和。

结论 1：每一轮循环都会正确计算当前位的数字

由于链表逆序存储，第 k 个节点表示数字的第 k 位，也就是从低位往高位数的第 k 位。

算法第 k 轮会读取两个链表的第 k 个节点。

如果某个链表已经结束，就相当于这一位是 0。

再加上上一位传来的 carry，得到当前位总和 sum。

根据十进制加法规则，当前结果位应该是：

sum % 10

新的进位应该是：

sum / 10

这正是代码所做的事情。

所以每一轮循环都会正确计算当前位。

结论 2：进位会被正确传递到下一位

每轮循环结束时，代码执行：

carry = sum / 10;

这个值就是当前位相加后产生的十进制进位。

下一轮开始时：

int sum = carry;

会先把这个进位加入下一位计算。

因此进位不会丢失。

如果所有链表节点都处理完后仍有进位，循环条件中的 carry != 0 会继续生成最后一个节点。

所以最高位进位也能被正确处理。

结论 3：结果链表的顺序符合题意

算法从低位到高位依次生成结果节点。

而题目要求返回的链表也按逆序存储，即低位在前，高位在后。

因此生成节点的顺序正好就是结果链表应该保存的顺序。

得出结论

由结论 1 可知，每一位的数字计算正确。

由结论 2 可知，所有进位都被正确传递和处理。

由结论 3 可知，结果链表的存储顺序符合题意。

因此算法正确。

举例理解

以：

l1 = [2,4,3]
l2 = [5,6,4]

为例。

它们分别表示：

342 和 465

逐位相加过程如下：

位数 l1 当前值 l2 当前值 进位 总和 当前节点 新进位
个位 2 5 0 7 7 0
十位 4 6 0 10 0 1
百位 3 4 1 8 8 0

最终结果链表是：

[7,0,8]

它表示：

807

复杂度分析

设两个链表长度分别为 m 和 n。

算法最多遍历两个链表各一次。

所以时间复杂度是：

O(max(m, n))

结果链表需要存储相加后的每一位。

如果不把返回结果占用的空间计入额外空间，算法只使用常数个变量。

所以额外空间复杂度是：

`O(1)