两数相加

中等

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

题解

定义单链表的构造函数，需要判断有没有传入val和next，如果没有，val默认等于0，next默认等于null

javascript

// 单链表的定义
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

算法如下

javascript

function addTwoNumbers(l1, l2) {
  let addOne = 0;
  let sum = new ListNode("0");
  let head = sum;
  while (addOne || l1 || l2) {
    let val1 = l1!==null ? l1.val : 0;
    let val2 = l2!==null ? l2.val : 0;
    let r1 = val1 + val2 + addOne;
    addOne = r1 >= 10 ? 1 : 0;
    sum.next = new ListNode(r1 % 10);
    sum = sum.next;
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  return head.next;
}

算法解析

由于数据是逆序存储的，所以第一位是个位，第二个是十位，第三位是百位...
- 例如[2 ,4, 3]，个位是2，十位是4，百位是3，也就是342
需要一个保存进位的变量，如果上一位相加的结果有进位，则把该变量赋值为1，若没有则把该变量赋值为0
使用while循环，把两个链表从个位开始，每一位进行相加，然后相加的结果一步步赋值到一个新的链表
- 注意每次相加时还要加上进位变量的值，一开始个位相加时进位变量的值为0
- 如果每次相加的结果大于10，说明需要进位
- 需要进位则把进位变量的值设置为1，把相加的结果对10进行取余并赋值给新链表的next
- 每次循环完需要把l1，l2和新链表分别指向它们的next

例如有以下两个链表
l1: [2,4,3]
l2: [5,6,4]

新建一个表示进位的变量addOne和一个新链表sum
addOne = 0
sum = []

第一次循环
l1的个位:2 + l2的个位:5 + addOne:0 = 7
7 < 10，不需要进位，addOne = 0
新链表个位的值为 7 % 10 = 7，sum = [7]
l1 = [4,3]
l2 = [6,4]

第二次循环
l1的十位:4 + l2的十位:6 + addOne:0 = 10
10 >= 10，需要进位，addOne = 1
新链表十位的值为 10 % 10 = 0，sum = [7, 0]
l1 = [3]
l2 = [4]

第三次循环
l1的百位:3 + l2的百位:4 + addOne:1 = 8
8 < 10，不需要进位，addOne=0
新链表百位的值为 8 % 10 = 8，sum = [7, 0, 8]
l1 = []
l2 = []
循环结束

两数相加 ​

题解 ​

两数相加

题解