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

    示例：

    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

    输出：7 -> 0 -> 8

    原因：342 + 465 = 807

    链接：https://leetcode-cn.com/problems/add-two-numbers

    输入：[2,4,3] , [5,6,4]
    输出： [7,0,8]

    我的解法：

    1. /**
    2. * 构造链表数据结构
    3. */
    4. function ListNode (val) {
    5.     this.val = val
    6.   this.next = null
    7. }
    9. /*
    10. * 获取链表长度
    11. * @param {ListNode} listNode类型数据
    12. */
    13. function getLength (ListNode) {
    14.     let len = 0
    15.   let temp = ListNode
    16.      while(temp) {
    17.     len++
    18.     temp = temp.next
    19.   }
    20.   return len
    21. }
    22. /*
    23. * listNode转化为数组
    24. * @param {ListNode}
    25. * @return Array
    26. */
    27. function listNodeToArr (ListNode) {
    28.     const arr = []
    29.   let next = ListNode
    30.   while (next) {
    31.       arr.push(next.val)
    32.     next = next.next
    33.   }
    34.   return arr
    35. }
    36. /*
    37. * 递归调用产生listNode 格式
    38. * @param Array|Number
    39. * @return {ListNode}
    40. */
    41. function generatelistNode (arr) {
    42.       if(!arr.length) return null
    43.     let node = new ListNode(arr.shift())
    44.     node.next = generatelistNode(arr)
    45.     return node
    46. }
    48. function addTwoNumbers (l1, l2) {
    49.   if (!l1 || !l2) return l1 ? l2 : l1
    50.   // 获取里两个链表对应长度，对短链表末位补零
    51.   const len1 = getLength(l1)
    52.   const len2 = getLength(l2)
    53.   let l1Arr, l2Arr
    54.   if (len1 !== len2) {
    55.     // 需要补的位数
    56.     let degits = Math.abs(len1 - len2)
    57.     // 构造出需要补位的数据
    58.     // ListNode 转数组，再转会listNode
    59.     l1Arr = len1 > len2 ? listNodeToArr(l1) : listNodeToArr(l1).concat(Array(degits).fill(0))
    60.     l2Arr = len1 > len2 ? listNodeToArr(l2).concat(Array(degits).fill(0)) : listNodeToArr(l2)
    61.   } else {
    62.       l1Arr = listNodeToArr(l1)
    63.     l2Arr = listNodeToArr(l2)
    64.   }
    65.   console.log('l1Arr, l2Arr ---', l1Arr, l2Arr)
    66.   // 拿到连个等长的数组，开始逐一相加，产生进位，向后加一 (因为是逆序)
    67.   const result = []
    68.   let carry = 0
    69.   let l1ArrFirst = l1Arr.shift() // 每次取数组第一位
    70.   let l2ArrFirst = l2Arr.shift()
    71.   while (l1ArrFirst !== undefined || l2ArrFirst !== undefined || carry) {
    72.     const sum = (l1ArrFirst || 0) + (l2ArrFirst || 0) + carry
    73.         if (sum >= 10) {
    74.             carry = 1
    75.       result.push(sum % 10)
    76.         }    else {
    77.         carry = 0
    78.       result.push(sum)
    79.     }
    80.     l1ArrFirst = l1Arr.length ? l1Arr.shift() : undefined// 每次取数组第一位
    81.       l2ArrFirst = l2Arr.length ? l2Arr.shift() : undefined
    82.     }
    83.   // 拿到倒序的数组，构造成listNode链表格式
    84.   // console.log('result ---', result, Array.isArray(result))
    85.   const final = generatelistNode(result)
    86.   // console.log('最终链表是：', final)
    87.   return final
    88. }
    89. // 构造数据
    90. const l1 = new ListNode(2)
    91. const l1x = new ListNode(4)
    92. const l1y = new ListNode(3)
    93. const l1z = new ListNode(5)
    94. l1.next = l1x
    95. l1x.next = l1y
    96. l1y.next = l1z
    98. const l2 = new ListNode(5)
    99. const l2x = new ListNode(6)
    100. const l2y = new ListNode(4)
    101. l2.next = l2x
    102. l2x.next = l2y
    103. addTwoNumbers(l1, l2)

    去掉链表补齐的操作后
    image.png

    优秀答案：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * function ListNode(val, next) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.next = (next===undefined ? null : next)
    6.  * }
    7.  */
    8. /**
    9.  * @param {ListNode} l1
    10.  * @param {ListNode} l2
    11.  * @return {ListNode}
    12.  */
    13. var addTwoNumbers = function(l1, l2) {
    14.     let addOne = 0
    15.     let sum = new ListNode('0')
    16.     let head = sum
    17.     while (addOne || l1 || l2) {
    18.         let val1 = l1 !== null ? l1.val : 0
    19.         let val2 = l2 !== null ? l2.val : 0
    20.         let r1 = val1 + val2 + addOne
    21.         addOne = r1 >= 10 ? 1 : 0
    22.         sum.next = new ListNode(r1 % 10)
    23.         sum = sum.next 
    24.         if (l1) l1 = l1.next 
    25.         if (l2) l2 = l2.next 
    26.     }
    27.     return head.next
    28. };
    30. 作者：afeng-xiu
    31. 链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-ge-shu-xiang-jia-zui-rong-yi-li-jie-de-jie-f/