跳至主要內容

2. 两数相加


2. 两数相加

🟠   🔖  递归 链表 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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
  • 题目数据保证列表表示的数字不含前导零

解题思路

  1. 初始化:

    • 创建一个新的链表 List 来存储结果,headList 的指针,用来遍历和构建结果链表。
    • 使用 sum 来存储每次两位数相加后的和,carry 来存储每次计算是否有进位。
  2. 遍历两个链表:

    • 使用 while 循环,当 l1l2 还存在节点或者 sum > 0 时,继续遍历。
    • 对于每一位数,分别从 l1l2 中提取当前节点的值,如果该链表为空,跳过。
    • 将当前位数相加,并检查是否有进位。
  3. 进位处理:

    • 如果 sum 大于或等于 10,表示有进位。设置 carry = 1,并更新 sumsum - 10
    • 否则,carry 设为 0。
  4. 构建结果链表:

    • 将当前位的和(去除进位后)保存到 head.next 中,并更新 head 指向下一个节点。
    • 处理完一个节点后,更新 sumcarry,以便下一轮加法使用。
  5. 返回结果:

    • 最后返回 List.next,即从头节点后的第一个节点开始的链表。

复杂度分析

  • 时间复杂度O(max(m, n)),其中 mn 分别是两个链表 l1l2 的长度。我们遍历两个链表一次,因此时间复杂度是它们长度的最大值。
  • 空间复杂度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字符串相乘[✓]数学 字符串 模拟🟠🀄️open in new window 🔗open in new window
67二进制求和[✓]位运算 数学 字符串 1+🟢🀄️open in new window 🔗open in new window
371两整数之和位运算 数学🟠🀄️open in new window 🔗open in new window
415字符串相加[✓]数学 字符串 模拟🟢🀄️open in new window 🔗open in new window
445两数相加 II[✓] 链表 数学🟠🀄️open in new window 🔗open in new window
989数组形式的整数加法[✓]数组 数学🟢🀄️open in new window 🔗open in new window
1634求两个多项式链表的和 🔒链表 数学 双指针🟠🀄️open in new window 🔗open in new window
2816翻倍以链表形式表示的数字 链表 数学🟠🀄️open in new window 🔗open in new window