2. Add Two Numbers

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

分析和方案

题目给出两个非空的链表数据，从右到左依次为个位 -> 十位 -> 百位 -> ...等等

返回结果也许要是一个链表数据，是两个输入值的合。

算法（第4版） (豆瓣)一书中对链表的定义如下：

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

在应用中，就是从头部取值，相加，判断是否需要进位，然后继续取值相加。塞入一个临时的链表，最后返回

/**
 * 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) {
    var add = 0
    , ans
    , head;

  while(l1 || l2) {
    var a = l1 ? l1.val : 0
      , b = l2 ? l2.val : 0;

    var sum = a + b + add;
    add = ~~(sum / 10);

    var node = new ListNode(sum % 10);

    if (!ans)
      ans = head = node;
    else {
      head.next = node;
      head = node; 
    }

    if (l1)
      l1 = l1.next;
    if (l2)
      l2 = l2.next;
  }

  if (add) {
    var node = new ListNode(add);
    head.next = node;
    head = node;
  }

  return ans;
};

下面这个是性能最佳的解法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2, addOne = false) => {
  if (!l1 && !l2) return addOne ? new ListNode(1) : null;
  const sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + (addOne ? 1 : 0);
  const node = new ListNode(sum % 10);
  node.next = addTwoNumbers(l1 ? l1.next : null, l2 ? l2.next : null, sum > 9);
  return node;
};