原题地址：两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入： (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
原因： 342 + 465 = 807
准备工作
定义链表的节点ListNode：
function ListNode(val) {
this.val = val;
this.next = null;
}
然后再定义一个将数组转换为链表的方法，方便后续测试时的数据录入：
function arrayToList(array) {
let node = null;
for (let i = array.length - 1; i >= 0; i --) {
let newNode = new ListNode(array[i]);
newNode.next = node;
node = newNode;
}
return node;
}
重写ListNode的toString()方法，方便输出测试结果：
ListNode.prototype = {
toString: function() {
return `${this.val}${this.next ? ` -> ${this.next.toString()}` : '' }`;
}
};
转换为Number
既然是计算两个整数的加法，我们就可以将两个链表转换为对应的整数，然后按整数进行加法运算，再将结果转换回链表即可：
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const addTwoNumbers1 = function(l1, l2) {
// 链表转换为Number
const nodeToNumber = (node) => {
let [multiple, result] = [1, 0]; // [倍数, 结果]
while (node) {
// 链表是逆序的，所以node每往后移一位，倍率乘以10
// 2 -> 4 -> 3 => 2 * 1 + 4 * 10 + 3 * 100 = 342
result += (node.val * multiple);
multiple *= 10;
node = node.next;
}
return result;
};
// Number转换为链表
const numberToNode = (value) => {
if (value === 0) {
return new ListNode(0);
}
let [node, lastNode] = [null, null]; // [头结点, 尾结点]
while (value > 0) {
// 注意要得到的是逆序链表，所以每次取余得到的值都是新的尾结点
let newNode = new ListNode(value % 10); // 取余
if (lastNode) {
lastNode.next = newNode; // 尾结点的next指向新的结点
lastNode = newNode; // 然后再将新结点作为新的尾结点
} else {
[node, lastNode] = [newNode, newNode]; // 初始时头结点和尾结点都指向新结点
}
value = Math.floor(value / 10); // 整除10
}
return node;
};
const result = nodeToNumber(l1) + nodeToNumber(l2);
return numberToNode(result);
};
但该方法有一个致命的缺陷，就是在数据过大时会发生溢出，导致计算结果不正确：
let start = new Date();
let test = addTwoNumbers1;
console.log(test(
arrayToList([9,4,3]),
arrayToList([9,4,3]),
).toString()); // 8 -> 9 -> 6
console.log(test(
arrayToList([0]),
arrayToList([0]),
).toString()); // 0
console.log(test(
arrayToList([1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]),
arrayToList([5,6,4]),
).toString()); // 数据溢出，结果错误，输出8 -> 6 -> 2 -> 2 -> 4 -> 4 -> 2 -> 8 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 1
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 两次转换，链接循环了两次，时间复杂度为O(max(m,n))
空间复杂度： 新的链表不会长度不会超过max(m,n) + 1,空间复杂度为O(max(m,n))
直接计算
由于链表存储整数的各位时是逆序的，所以遍历链表就相当于从低位往高位遍历整数的各位，这与加法运算的规则是一致的。所以只需要正常遍历两个链表，按加法的规则进行计算，并处理好进位即可：
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const addTwoNumbers2 = function(l1, l2) {
let [node, lastNode, cache] = [null, null, 0]; // [头结点，尾结点，缓存值（用来存储加法产生的进位）]
while (l1 || l2 || cache) { // 任一链表有值或者是还有进位存在
if (l1) {
cache += l1.val;
l1 = l1.next;
}
if (l2) {
cache += l2.val;
l2 = l2.next;
}
let newNode = new ListNode(cache % 10);
if (lastNode) {
lastNode.next = newNode; // 尾结点的next指向新的结点
lastNode = newNode; // 然后再将新结点作为新的尾结点
} else {
[node, lastNode] = [newNode, newNode]; // 初始时头结点和尾结点都指向新结点
}
cache = cache > 9; // 利用这一判断将cache转为boolean，后续再进行加法运算时会自动转换为Number的0和1
}
return node;
};
测试：
let start = new Date();
let test = addTwoNumbers2;
console.log(test(
arrayToList([9,4,3]),
arrayToList([9,4,3]),
).toString()); // 8 -> 9 -> 6
console.log(test(
arrayToList([0]),
arrayToList([0]),
).toString()); // 0
console.log(test(
arrayToList([1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]),
arrayToList([5,6,4]),
).toString()); // 6 -> 6 -> 4 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 1
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 两个链表各遍历了一次，时间复杂度为O(max(m,n))
空间复杂度： 空间复杂度为O(max(m,n))
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 6,2019