题目描述:
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序
的方式存储的,并且它们的每个节点只能存储一位
数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
ListNode类是这样的,也就是一个链表每一个节点都是new ListNode
出来的,而且如果有下一个节点,那么它的next就是new
出来的一个新的ListNode
function ListNode(val) {
this.val = val;
this.next = null;
}
复制代码
基于此,我们先写一个创建链表的函数,方便测试:
const res = new ListNode();
let temp = res;
arr.forEach((i, j) => {
temp.val = i;
if (j !== arr.length - 1) {
temp = temp.next = new ListNode();
}
});
return res;
}
复制代码
题目已经给了我们倒序了,那么就相当于创造了一个天然的加法环境——算术都是从右边开始算。接下来,我们先同时遍历两个链表
isMoreThan10
为truenew ListNode(1)
节点function addTwoNumbers(l1, l2) {
let res;
let temp; // 当前的节点
let isMoreThan10 = false;
while (l1 && l2) { // 两个链表公共部分
const sum = l1.val + l2.val;
const r = sum % 10;
if (temp) {
// 一边创建一边取下一个
temp.next = new ListNode();
temp = temp.next;
}
if (!res) {
// 第一次进来
res = new ListNode(r);
temp = res;
}
// 所有的加法操作都要这样
temp.val = (r + isMoreThan10) % 10;
isMoreThan10 = sum + isMoreThan10 > 9;
l1 = l1.next;
l2 = l2.next;
}
// 剩下那段
let rest = l1 || l2;
while (rest) {
temp.next = rest;
temp = temp.next;
if (isMoreThan10) {
isMoreThan10 = temp.val + 1 > 9;
temp.val = (temp.val + 1) % 10;
}
rest = rest.next;
}
// 如果还有进位,追加一个1
if (isMoreThan10) {
temp.next = new ListNode(1);
}
return res;
}
复制代码
两个很大的数字,大到失去精度的情况,就不能直接使用数字来相加了。es10有bigint可以瞬间解决,这里不列举了。他们的相加,需要操作字符串来实现。
还是类似的过程:
function add(a, b) {
let cursor = 1;
const [{ length: aLen }, { length: bLen }] = [a, b];
let res = "";
let carry = 0;
while (a[aLen - cursor] && b[bLen - cursor]) {
// 共同位数
const sum = +a[aLen - cursor] + +b[bLen - cursor] + carry;
// 取个位数拼接到最终结果前面
res = `${sum % 10}${res}`;
// 进位标志
carry = +(sum > 9);
cursor++;
}
// 剩下是a的处理
while (a[aLen - cursor]) {
const sum = +a[aLen - cursor] + carry;
res = `${sum % 10}${res}`;
carry = +(sum > 9);
cursor++;
}
// 剩下是b的处理
while (b[bLen - cursor]) {
const sum = +b[bLen - cursor] + carry;
res = `${sum % 10}${res}`;
carry = +(sum > 9);
cursor++;
}
return `${carry || ""}${res}`;
}
复制代码
整体套路是差不多的,不过上面的代码有点冗余,剩余的a和b那段是一样的套路,甚至最后剩余一个进位还是一样的操作。我们可以优化一下,把这些代码复用起来
function add(a, b) {
let cursor = 1;
const [{ length: aLen }, { length: bLen }] = [a, b];
let res = "";
let carry = 0;
// 全部case合并过来
while (a[aLen - cursor] || b[bLen - cursor] || carry) {
// ~~的妙处:可以把undefined转为0
const sum = ~~a[aLen - cursor] + ~~b[bLen - cursor] + carry;
res = `${sum % 10}${res}`;
carry = +(sum > 9);
cursor++;
}
return res;
}
复制代码
拓展,多个大数相加支持
while判断有a[aLen - cursor] || b[bLen - cursor]
,那么多个的话,对应的就是数组的some方法了: arr.some(condition)
返回对每一个数组元素执行condition
后的返回值,只要有一个是true,最终结果就是true,相当于condition(arr[0]) || condition(arr[1]) || condition(arr[2]) || ....
个位数的求和,使用reduce求和即可,最后补上一个进位。优化:args.some
如果是false,不走reduce,可以自己去测试一下执行时间。
// 从写死两个到数组
function addMany(...args) {
let cursor = 1;
let res = "";
let carry = 0;
while (args.some(arg => arg[arg.length - cursor]) || carry) {
const sum =
args.reduce((acc, arg) => acc + ~~arg[arg.length - cursor], 0) + carry;
res = `${sum % 10}${res}`;
carry = ~~(sum / 10);
cursor++;
}
return res;
}
复制代码