# 题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
输入:(2 -> 4 -> 3 -> 1) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8 -> 1
原因:1342 + 465 = 1807
# 解题思路
- 先将输入的两个链表
l1
和l2
转换为数组; - 将两个数组进行相加(要考虑到进位);
- 将相加后的数组转换为链表.
注⚠️:
我开始想的是将两个链表转换为数字,然后进行数字相加后,用相加的总和转换为数组.但若是相加的总和非常大则达不到预期的效果.如第一个数字是100000000000000001
,第二个数字是543
,就会造成结果不对.
所以这里将链表转成数字进行计算.
# coding
/**
* Definition for singly-linked list.
*/
function ListNode(val) {
this.val = val;
this.next = null;
}
/**
* 把链表转换为数组
*/
function transformListToArray(node) {
let array = []
while (node) {
array.push(node.val)
node = node.next
}
return array
}
/**
* 把数组转换为链表
*/
function transformArrayToList(array) {
// let array = num.toString().split('').reverse()
function createList(array) {
if (array.length === 0) return null
let list = new ListNode(array[0])
array.shift()
list.next = createList(array)
return list
}
return createList(array)
}
//两个数组相加
var addArray = function(arr1, arr2) {
var jdg = false, // 是否需要进位
newArr = [],
sum = null,
num = null,
len = Math.max(arr1.length, arr2.length);
for (i = 0; i < len; i++) {
sum = (arr1[i] ? arr1[i] : 0) + (arr2[i] ? arr2[i] : 0) + (jdg ? 1 : 0);
num = sum % 10;
jdg = (sum >= 10);
newArr.push(num);
}
if (jdg) {
newArr.push(1);
}
return newArr;
}
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var a1 = transformListToArray(l1)
var a2 = transformListToArray(l2)
var arr = addArray(a1, a2)
return transformArrayToList(arr)
}
用时140ms,内存消耗39.1MB.
上面的并不是最优解, 相比与上面,下面的写法性能更加好:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let result = new ListNode(null);
let nextRst = result;
// 进位
let params = 0 // 传给下一个层级的值
let val = 0 // 传给当前层级的值
while(l1 != null || l2 != null) {
// TODO
let x = (l1 != null) ? l1.val : 0;
let y = (l2 != null) ? l2.val : 0;
val = (x + y + params) % 10;
params = Math.floor((x + y + params) / 10); // 是否有进位 0 或者 1
nextRst.next = new ListNode(val)
nextRst = nextRst.next
if(l1 != null) l1 = l1.next
if(l2 != null) l2 = l2.next
}
if(params) {
nextRst.next = new ListNode(params)
}
return result.next
};
用时120ms,内存消耗38.4MB.
下面是测试代码:
let l1 = transformArrayToList([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2])
let l2 = transformArrayToList([5, 6, 4])
console.log(addTwoNumbers(l1, l2))
阅读全文