两数之和

算法思路

由于从加法从最后节点开始运算，所以我们可以用栈存，然后出栈做加法，生成节点就可以了。

数组转链表

/** arr to reveser Link Node */
const arrTransToLink = (arr) => {
  let ans = null;
  let i = 0;
  while (i < arr.length) {
    let curNode = new ListNode(arr[i]);
    curNode.next = ans;
    ans = curNode;
    i++;
  }
  //  return arrTransToLink([1,2,3])  1->2->3
  return ans;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

const transToArrAndRevert = (link) => {
  const arr = [];

  while (link) {
    arr.push(Number(link.val));
    link = link.next;
  }

  return arr.reverse();
};

const addZero = (arr, len) => {
  while (len) {
    arr.push(0);
    len--;
  }
};

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  // 反转两个链表
  const linkArr1 = transToArrAndRevert(l1);
  const linkArr2 = transToArrAndRevert(l2);

  // 补零

  const len = linkArr1.length - linkArr2.length;

  if (len > 0) {
    addZero(linkArr2, len);
  } else if (len < 0) {
    addZero(linkArr1, Math.abs(len));
  }

  let step = 0;
  let res = [];

  for (let i = 0; i < linkArr1.length; i++) {
    const sum = linkArr1[i] + linkArr2[i] + step;

    if (sum > 9) {
      res.unshift(sum - 10);
      step = 1;
    } else {
      res.unshift(sum);
      step = 0;
    }
  }
  if (step === 1) {
    res.unshift(1);
  }

  // 创建一个链表

  let header = new ListNode(res[0]);
  let p = header;
  let l = 1;

  while (l < res.length) {
    p.next = new ListNode(res[l]);
    p = p.next;
    l++;
  }

  return header;
};