2. 两数相加

这个题目需要使用 js 来实现单项列表，并把两个链表的每一项相加，返回一个新的链表。

题目地址

描述

解析

既然是要用列表来操作，那我们首先应该定义列表。
从题目的注释中我们可以看到已经给我们定义好结构了

 //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) {
  const currNode1 = l1
  const currNode2 = l2
  let num1 = 0; let num2 = 0
  let i = 0
  let currNode = currNode1
  while (currNode.next) {
    num1 += currNode.val * (Math.pow(10, i))
    currNode = currNode.next
    i++
  }
  num1 += currNode.val * (Math.pow(10, i))
  console.log({ num1 })
  i = 0
  currNode = currNode2
  while (currNode.next) {
    num2 += currNode.val * (Math.pow(10, i))
    currNode = currNode.next
    i++
  }
  num2 += currNode.val * (Math.pow(10, i))
  console.log({ num2 })

  let sum = 0
  let tmp = 0

  sum = num1 + num2
  console.log({ sum })

  currNode = new ListNode(0)

  tmp = sum % 10
  sum = parseInt(sum / 10)
  const resNode = new ListNode(tmp)
  currNode = resNode

  while (sum >= 1) {
    tmp = sum % 10
    sum = parseInt(sum / 10)
    const tmpNode = new ListNode(tmp)
    currNode.next = tmpNode
    currNode = tmpNode
  }

  return resNode
}

这个代码初看没有问题，而且在数组项较少时没有问题
如

addTwoNumbers([2, 6], [1, 2, 3])

输出：

[3, 8, 3]

可是当我们的数组项较多时，就不可行了。

const nodeList1 = createListNodeFromArray()
const nodeList2 = createListNodeFromArray([5, 6, 4])

const nodeList = addTwoNumbers([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], [5,6,4])

这个时候再转成整型，已经超出了最大范围。

所以这种方法不可行

二、 按位相加

很自然的，我们就想到了按位相加这种方法。
按位相加，需要考虑两个数之和大于10时，需要进一。

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let currNode1 = l1
  let currNode2 = l2
  let tmp = 0
  let intoOne = 0
  let val1 = 0
  let val2 = 0

  const retNode = new ListNode(0)
  let currNode = retNode
  let tmpNode = null
  while (true) {
    val1 = currNode1 ? currNode1.val : 0
    val2 = currNode2 ? currNode2.val : 0
    tmp = val1 + val2 + intoOne
    if (tmp >= 10) {
      // 进1
      tmp -= 10
      intoOne = 1
    } else {
      intoOne = 0
    }

    if (currNode == null) {
      currNode = new ListNode(tmp)
    } else {
      tmpNode = new ListNode(tmp)
      currNode.next = tmpNode
      currNode = tmpNode
    }

    currNode1 = currNode1 && currNode1.next
    currNode2 = currNode2 && currNode2.next
    if (currNode1 == null && currNode2 == null) {
      break
    }
  }

  return retNode.next
}

上面的代码也是有问题的。就是没有考虑最后一项相加时大于10的情况。

addTwoNumbers([5], [5])

输出：

错误：
[0]

正确：
[0, 1]

针对这种情况，需要在循环结束之后判断最后一项是否大于10

  if (intoOne === 1) {
    tmpNode = new ListNode(1)
    currNode.next = tmpNode
    currNode = tmpNode
  }

完整代码如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

function ListNode (val) {
  this.val = val
  this.next = null
}

function createListNodeFromArray (arr) {
  const headerNode = new ListNode(arr[0])
  let currNode = headerNode

  for (let i = 1; i < arr.length; i++) {
    const element = arr[i]

    const tmpNode = new ListNode(element)
    currNode.next = tmpNode
    currNode = tmpNode
  }

  return headerNode
}

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let currNode1 = l1
  let currNode2 = l2
  let tmp = 0
  let intoOne = 0
  let val1 = 0
  let val2 = 0

  const retNode = new ListNode(0)
  let currNode = retNode
  let tmpNode = null
  while (true) {
    val1 = currNode1 ? currNode1.val : 0
    val2 = currNode2 ? currNode2.val : 0
    tmp = val1 + val2 + intoOne
    if (tmp >= 10) {
      tmp -= 10
      intoOne = 1
    } else {
      intoOne = 0
    }

    if (currNode == null) {
      currNode = new ListNode(tmp)
    } else {
      tmpNode = new ListNode(tmp)
      currNode.next = tmpNode
      currNode = tmpNode
    }

    currNode1 = currNode1 && currNode1.next
    currNode2 = currNode2 && currNode2.next
    if (currNode1 == null && currNode2 == null) {
      break
    }
  }
  if (intoOne === 1) {
    tmpNode = new ListNode(1)
    currNode.next = tmpNode
    currNode = tmpNode
  }
  return retNode.next
}

const nodeList1 = createListNodeFromArray([2, 4, 3])
const nodeList2 = createListNodeFromArray([5, 6, 7])

const nodeList = addTwoNumbers(nodeList1, nodeList2)

let currNode = nodeList
while (currNode.next) {
  console.log(currNode.val)
  currNode = currNode.next
}
console.log(currNode.val)