Add two numbers

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.

/**
 * 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;
};

Add two numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

"use strict";

/**
 * 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 a = []
    , b = []
    , newL1 = l1
    , newL2 = l2;

  while (newL1) {
    a.push(newL1.val);
    newL1 = newL1.next;
  }

  while (newL2) {
    b.push(newL2.val);
    newL2 = newL2.next;
  }

  a.reverse();
  b.reverse();

  let ans = [];
  let add = 0;

  while (a.length || b.length) {
    let c = a.length ? a.shift() : 0;
    let d = b.length ? b.shift() : 0;
    let sum = c + d + add;

    ans.push(sum % 10);
    add = ~~(sum / 10);
  }

  add && (ans.push(add));

  ans.reverse();

  let ret = [];

  for (let i = 0, len = ans.length; i < len; i++)
    ret[i] = new ListNode(ans[i]);

  for (let i = 0, len = ans.length; i < len - 1; i++)
    ret[i].next = ret[i + 1];

  return ret[0];
};

Additive number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:

“112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Follow up:

How would you handle overflow for very large input integers?

/**
 * @param {string} num
 * @return {boolean}
 */

// use Depth-First-Search Algorithm

var ans;

function dfs(a, b, c, index, num) {
  if (ans)
    return;

  if (index === num.length) {
    if (a === -1 || b === -1 || c === -1)
      return;
    if ((+a) + (+b) === (+c))
      ans = true;
    return;
  }

  if (a === -1) {
    dfs(num[index], b, c, index + 1, num);
    return;
  }

  if (b === -1) {
    if (a !== '0')
      dfs(a + num[index], b, c, index + 1, num);

    dfs(a, num[index], c, index + 1, num);

    return;
  }

  if (c === -1) {
    if (b !== '0')
      dfs(a, b + num[index], c, index + 1, num);

    dfs(a, b, num[index], index + 1, num);
    return;
  }

  if (c !== '0') {
    if ((+a) + (+b) === (+c)) {
      dfs(b, c, -1, index, num);
    } else {
      if ((+a) + (+b) < (+c))
        return;
      dfs(a, b, c + num[index], index + 1, num);
    }
  } else {
    if (a === '0' && b === '0')
      dfs(b, c, -1, index, num);
  }
}

var isAdditiveNumber = function(num) {
  ans = false;
  dfs(-1, -1, -1, 0, num);
  return ans;
};