「算法」「2.两数相加」leetcode初次接触链表

2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

咋看之下题目真的是不能理解，不知所云，想表达什么。其实是因为题目给的示例是有问题的。如果将示例改为：
输入：（2 -> 4 -> 3）+（4 -> 6 -> 6）
输出： 6 -> 0 -> 0 -> 1
原因：342 + 664 = 1006

这是leetcode的第二题，难度和第一题比起来难度提升了一些，这也是一道偏简单的中等题。考点在于链表对合并对下一位数的影响
有优化过后的题目说明，题目的考点变得了更加明朗了。

谈谈我自己的解题思路。
1）最基础的遍历时一次访问两个链表的元素，对于相加小于10的数就直接放置，对于相加大于10的数，余数放置，临时存储一个 1 到下一位。类似于小学学加减法一样，考点便是对链表进行的一些边界情况的操作。
2）除了上面的基础操作外，我们其实应该避免新建链表进行存值，将新的值存入到我们已经使用过的链表上，比如l1，因为在进行运算过后，我们并不会再使用链表的这些位置了。

代码写的逻辑易懂，但并不是最优解，仅做学习参考。leetcode上有更简洁的代码。

/**
 * 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 dyH1 = new ListNode() //创建虚拟头连接l1，方便进行操作
    let dyH2 = new ListNode() //创建虚拟头连接l2
    dyH1.next = l1
    dyH2.next = l2

    let tmp = 0, sums = 0 //tmp保存的是进到下一位临时保存的十位数 1，sums用于存储和
    let ret = l1 //因为虚拟头在操作中会不断变化，所以保留l1的第一位元素方便返回
    while(dyH1.next || dyH2.next || tmp) {//当l1链表，l2链表，进十位的临时数里还有数时，我们继续循环
        if(dyH1.next && dyH2.next) {//此时两个链表都还有值，所以继续循环
            sums = dyH1.next.val + dyH2.next.val + tmp   //对两个列表的取值求和，如果有来自上一位的十位数则加上。
            dyH1.next.val = parseInt(sums % 10) //计算保留在个位的数
            tmp = parseInt(sums / 10) //计算是否需要向下一位进10
            dyH1 = dyH1.next //两个链表同时向后移动一个节点，继续循环
            dyH2 = dyH2.next
        }else if(dyH1.next) { //此时说明l2链表已经到头，检查是否还存在来自上一次循环的十位数
            if(tmp) { //存在则继续计算
                sums = tmp + dyH1.next.val
                tmp = parseInt(sums / 10)
                dyH1.next.val = parseInt(sums % 10)
                dyH1 = dyH1.next
            }else //不存在则直接跳出
                break
        } else if (dyH2.next) { //此时l1链表已经没有值了，直接将l2剩下的值转到l2上来，l2清空；即时十位数还存在值，在下次循环时也会被上一个条件拦截处理掉
            dyH1.next = dyH2.next
            dyH2.next = null
        } else { //此时l1，l2链表都没有了数，检查是否有十位数，有就新建node且跳出循环直接提交。
            dyH1.next = new ListNode(1)
            break;
        }
    }
    return ret
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。