445. Add Two Numbers II

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

  Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

  Constraints:

• The number of nodes in each linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• It is guaranteed that the list represents a number that does not have leading zeros.

  Follow up: Could you solve it without reversing the input lists?

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var r1 = reverse(l1);
    var r2 = reverse(l2);
    var root = new ListNode();
    var node = root;
    var carry = 0;
    var val = 0;
    while (r1 || r2) {
        val = (r1 ? r1.val : 0) + (r2 ? r2.val : 0) + carry;
        node.next = new ListNode(val % 10);
        node = node.next;
        carry = (val - node.val) / 10;
        r1 = r1 ? r1.next : null;
        r2 = r2 ? r2.next : null;
    }
    if (carry) {
        node.next = new ListNode(carry);
        node = node.next;
    }
    return reverse(root.next);
};

var reverse = function(root) {
    var node = root.next;
    var last = root;
    var tmp = null;
    last.next = null;
    while (node) {
        tmp = node.next;
        node.next = last;
        last = node;
        node = tmp;
    }
    return last;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).