2. 两数相加
2. 两数相加
题目
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order , and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]
. 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
题目大意
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
![](https://assets.leetcode-cn.com/aliyun-lc- upload/uploads/2021/01/02/addtwonumber1.jpg)
输入: 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
- 题目数据保证列表表示的数字不含前导零
解题思路
初始化:
- 创建一个新的链表
List
来存储结果,head
是List
的指针,用来遍历和构建结果链表。 - 使用
sum
来存储每次两位数相加后的和,carry
来存储每次计算是否有进位。
- 创建一个新的链表
遍历两个链表:
- 使用
while
循环,当l1
或l2
还存在节点或者sum > 0
时,继续遍历。 - 对于每一位数,分别从
l1
和l2
中提取当前节点的值,如果该链表为空,跳过。 - 将当前位数相加,并检查是否有进位。
- 使用
进位处理:
- 如果
sum
大于或等于 10,表示有进位。设置carry = 1
,并更新sum
为sum - 10
。 - 否则,
carry
设为 0。
- 如果
构建结果链表:
- 将当前位的和(去除进位后)保存到
head.next
中,并更新head
指向下一个节点。 - 处理完一个节点后,更新
sum
为carry
,以便下一轮加法使用。
- 将当前位的和(去除进位后)保存到
返回结果:
- 最后返回
List.next
,即从头节点后的第一个节点开始的链表。
- 最后返回
复杂度分析
- 时间复杂度:
O(max(m, n))
,其中m
和n
分别是两个链表l1
和l2
的长度。我们遍历两个链表一次,因此时间复杂度是它们长度的最大值。 - 空间复杂度:
O(max(m, n))
,因为需要存储返回的结果链表,它的长度最多为两个链表长度之和。
代码
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
var List = new ListNode(0); // 新建一个虚拟头节点
var head = List;
var sum = 0; // 当前位的和
var carry = 0; // 进位
while (l1 !== null || l2 !== null || sum > 0) {
if (l1 !== null) {
// 如果 l1 不为空
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
// 如果 l2 不为空
sum += l2.val;
l2 = l2.next;
}
if (sum >= 10) {
// 如果当前位的和大于或等于 10,需要进位
carry = 1;
sum -= 10; // 处理进位
}
head.next = new ListNode(sum);
head = head.next;
sum = carry; // 将进位传递给下一位
carry = 0; // 重置进位
}
return List.next; // 返回链表的实际结果部分(跳过虚拟头节点)
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
43 | 字符串相乘 | [✓] | 数学 字符串 模拟 | 🟠 | 🀄️ 🔗 |
67 | 二进制求和 | [✓] | 位运算 数学 字符串 1+ | 🟢 | 🀄️ 🔗 |
371 | 两整数之和 | 位运算 数学 | 🟠 | 🀄️ 🔗 | |
415 | 字符串相加 | [✓] | 数学 字符串 模拟 | 🟢 | 🀄️ 🔗 |
445 | 两数相加 II | [✓] | 栈 链表 数学 | 🟠 | 🀄️ 🔗 |
989 | 数组形式的整数加法 | [✓] | 数组 数学 | 🟢 | 🀄️ 🔗 |
1634 | 求两个多项式链表的和 🔒 | 链表 数学 双指针 | 🟠 | 🀄️ 🔗 | |
2816 | 翻倍以链表形式表示的数字 | 栈 链表 数学 | 🟠 | 🀄️ 🔗 |