[Leetcode]2.Add Two Numbers

2.Add Two Numbers

題目連結
難易度：Medium

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.

思路

Create a empty ListNode first, write a recursive function to dive into l1, l2 ListNode,
Caculate the sum of l1.val and l2.val and the carry from last node, only store the number 1~9 part in the
current node, pass carry to next node, re-run the function until l1 and l2 are all empty.

解題

/**
 * 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) {
    let list = new ListNode();
    let result = list;
    function addListNode(node1, node2, carry = 0){
        let sum = 0;
        if(!node1 && !node2 && carry === 0) return;
        if(node1){
            sum += node1.val;
            node1 = node1.next; // ready to calculate next node
        }
        if(node2){
            sum += node2.val;
            node2 = node2.next; // ready to calculate next node
        }
        sum += carry; // add last sum carry
        carry = (sum / 10) >= 1 ? 1 : 0 // if current sum > 10, carry is 1
        list.next = new ListNode(sum % 10); // store digit <10 part to next node
        list = list.next;
        addListNode(node1,node2,carry)
    }
    addListNode(l1,l2)
    return result.next // first node is an empty node, return next node
    
};