2、两数相加

2、两数相加

题意

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储

的，并且每个节点只能存储 一位 数字。

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

示例

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807

• l1 存储的是 2、4、3，也就是整数 342，逆序嘛；

• l2 存储的是 5、6、4，也就是整数 465，逆序嘛；

• 个位相加为 7（2+5），十位相加为 10（4+6，需要进位），百位相加为 7（3+4），

加上进位的 1 就是 8

002.%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0-20231210122104.png

难度

中等

分析

首先，搞清楚“逆序”是什么。

逆序：从后往前的顺序，比如 123 的逆序是 321。

题目中的示例其实也给出了解释，假如逆序链表 l1 为 [2,4,3]，l2 为 [5,6,4]，那么 l1 代

表的数字就是 342，l2 为 456。

对于还没有学过链表的球友来说，可以通过二哥的 Java 进阶之路中的 LinkedList

来学习一下链表的数据结构，大体上就这样：a->b->c->d

两数相加，如果不需要进位的话，就是把对应位置的数字相加，比如 342 + 456 = 798，

非常简单。

难点就在于，进位该如何处理。

回想一下我们小学曾经学过的加法竖式，如下图。

002.%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0-20231210152848.png

对于每一位上的数字相加，都有可能产生进位，比如 4 + 6 = 10，那么 1 就是进位，我们

需要把它加到下一位的和中即可。

假设两个链表相同位置的数字分别是 addX 和 addY，进位是 up，那么它们的和（sum）

就是 addX + addY + up，如果 sum 大于 10 的话，需要进位，那么进位的值就是 sum /

10，而 sum % 10 就是当前位置的数字。

比如说个位 7+8=15（此时进位为 0），由于和大于 10，所以十位的进位就是 1（sum /

10），个位的数字就是 5（sum % 10）。

十位 4+6+1=11（此时进位为 1），由于和大于 10，所以百位的进位就是 1（sum /

10）， 十位的数字就是 1（sum % 10）。

百位 3+5+1=9（此时进位为 1），由于和小于 10，所以千位的进位就是 0（sum / 10），

百位的数字就是 9（sum % 10）。

也就是说 347（对应的逆序链表为「7、4、3」）+568（对应的逆序链表为「8、6、

5」）=915（新的逆序链表为 5、1、9），这就是我们最终的结果。

• 7+8=15，进位为 1，个位为 5；

• 4+6+1=11，进位为 1，十位为 1；

• 3+5+1=9，进位为 0，百位为 9。

是不是突然发现，逆序链表的顺序和我们的计算顺序恰好是一样的，这样子就方便我们直

接进行处理。

假如不是逆序的，那么我们就需要先把链表反转，然后再进行计算，最后再把结果反转回

来。

妙啊！

/**

* 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; }

*}

*/

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode dummyHead = new ListNode(0); // 创建一个哨兵节点，方便返回结果

ListNode p = l1, q = l2, curr = dummyHead; // 初始化三个指针：p 和 q 分别遍历

两个输入链表，curr 用于构建结果链表

int carry = 0; // 初始化进位值为 0

// 遍历两个链表直到全部结束

while (p != null || q != null) {

// 获取当前节点的值，如果节点不存在则为 0

int x = (p != null) ? p.val : 0;

int y = (q != null) ? q.val : 0;

// 计算两个值和进位值的总和

int sum = carry + x + y;

// 更新进位值

carry = sum / 10;

 // 创建新节点，值为总和的个位数，并将其加入到结果链表

curr.next = new ListNode(sum % 10);

// 移动 curr 指针到新节点

curr = curr.next;

// 如果存在，移动 p 和 q 到各自链表的下一个节点

if (p != null) p = p.next;

if (q != null) q = q.next;

}

// 循环结束后，如果仍有进位，则在结果链表末尾添加一个节点

if (carry > 0) {

curr.next = new ListNode(carry);

}

// 返回哨兵节点的下一个节点，即结果链表的头节点

return dummyHead.next;

}

}

当输入是 l1 = [2,4,3] 和 l2 = [5,6,4] 时，我们来模拟一下整个题解过程：

1. 初始化：创建一个哨兵节点 dummyHead 用于简化边界情况的处理，以及一个临时

节点 curr 指向它。设置进位 carry 为 0。

2. 开始遍历两个链表：

– 第一轮迭代：

• l1 的当前元素是 2，l2 的当前元素是 5。

• 计算和：sum = 2 + 5 + 0 = 7（当前进位 carry 是 0）。

• 创建新节点，值为 sum % 10 = 7，进位 carry = sum / 10 = 0。

• 移动 curr 到新节点。

• 移动 l1 和 l2 分别到下一个节点。

– 第二轮迭代：

• l1 的当前元素是 4，l2 的当前元素是 6。

• 计算和：sum = 4 + 6 + 0 = 10（当前进位 carry 是 0）。

• 创建新节点，值为 sum % 10 = 0，进位 carry = sum / 10 = 1。

• 移动 curr 到新节点。

• 移动 l1 和 l2 分别到下一个节点。

– 第三轮迭代：

• l1 的当前元素是 3，l2 的当前元素是 4。

• 计算和：sum = 3 + 4 + 1 = 8（当前进位 carry 是 1）。

• 创建新节点，值为 sum % 10 = 8，进位 carry = sum / 10 = 0。

• 移动 curr 到新节点。

• l1 和 l2 都没有下一个节点，结束遍历。

3. 检查最后的进位：

– 检查 carry 是否大于 0。此处 carry = 0，所以不需要添加新节点。

4. 返回结果：

– 返回 dummyHead.next，即哨兵节点后的链表。结果为 7 -> 0 -> 8。

342+465=807，我们得到了正确的答案。

时间复杂度：$ O(max(l1.size,l2.size)) $

空间复杂度：$ O(max(l1.size,l2.size)) $

我擦嘞，竟然打败了 100% 的用户！

002.%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0-20231210155729.png

总结

本题其实是一个铺垫，就比如说给你了一个非常非常大的数，用 int、long 根本无法装

下，那其实就可以把这个数简化为一个链表，每个节点存储一个数位，这样子就可以无限

扩展了。

其实这道题的内核就是大数相加，只不过我们把大数用链表来表示了，并且题目限制了每

个链表中的节点数在范围 [1, 100] 内。

其实计算机中的大多数思想都是这样的，当一个问题超复杂时，我们就简化它，把它拆分

成一个个小问题，然后再去解决。

关于 while 循环和链表的知识，我这里补充一下学习资料。

• while 循环

• 链表（Linked list）

• LinkedList 和 ArrayList 的区别

力扣链接：https://leetcode.cn/problems/add-two-numbers/