Add Two Numbers

Problem

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 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

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

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

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constaints

• 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.

Solution

结点定义如下：

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

1. 直接思路，将两个单链表转成数字，然后将两数相加得和，再将和逆向转成单链表。

   /**
   * @param {ListNode} l1
   * @param {ListNode} l2
   * @return {ListNode}
   */
   var addTwoNumbers = function (l1, l2) {
    let arr1 = [], arr2 = [];
   
    while (l1) {
        // arr1.push(l1.val === undefined ? 0 : l1.val);
        arr1 = [...arr1, l1.val === undefined ? 0 : l1.val];
        l1 = l1.next;
    }
    while (l2) {
        arr2 = [...arr2, l2.val === undefined ? 0 : l2.val];
        l2 = l2.next;
    }
   
    let num1 = 0;
    let num2 = 0;
    for (let i = 0; i < arr1.length; i++) {
        num1 += Math.pow(10, i) * arr1[i];
    }
    for (let i = 0; i < arr2.length; i++) {
        num2 += Math.pow(10, i) * arr2[i];
    }
   
    let sum = num1 + num2;
    if (sum === 0) return new ListNode(0);
    let res = null;
    let child = null;
    for (let i = 1; sum > 0; i++) {
        const divider = Math.pow(10, i);
        const modNum = sum % divider;
        const val = new ListNode(modNum / (divider / 10));
        if (res === null) {
            res = val;
        }
   
        if (child !== null) {
            child.next = val;
        }
        child = val;
        sum -= modNum;
    }
   
    return res;
   };
   

   这种方式，输入参数代表的数字较小时是正确的，但是数值大会导致溢出。

2. 采用递归的方式，不会溢出

   var addTwoNumbers = function (l1, l2) {
    let node = null;
    const carry = arguments[2];
    if (l1 || l2) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const next1 = l1 ? l1.next : null;
        const next2 = l2 ? l2.next : null;
        const val = carry ? val1 + val2 + 1 : val1 + val2;
        node = new ListNode(val % 10);
        node.next = addTwoNumbers(next1, next2, val >= 10);
    } else if (carry) {
        node = new ListNode(1);
        node.next = null;
    }
    return node;
   };