# 题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

输入:(2 -> 4 -> 3 -> 1) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8 -> 1
原因:1342 + 465 = 1807

# 解题思路

  1. 先将输入的两个链表l1l2转换为数组;
  2. 将两个数组进行相加(要考虑到进位);
  3. 将相加后的数组转换为链表.

⚠️:

我开始想的是将两个链表转换为数字,然后进行数字相加后,用相加的总和转换为数组.但若是相加的总和非常大则达不到预期的效果.如第一个数字是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))
阅读全文