Leetcode - Medium - 2. Add Two Numbers - Javascript

Leetcode - Medium - 2. Add Two Numbers - Javascript

   清晨7:48       Rain Lin

---

 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.

 

Example 1:

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

 

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.

解題方向：

1. 須透過 linked list 方式取得下一個 node 的 value, 並傳遞進位到下一個計算中, 可透過遞迴方式解題 O(n)

解題注意地方：

1. 需使用題目提供的 linked list function 獲取 node 資訊

2. Carry 的取得方式如果透過 parseInt 會比直接 sum < 9 慢上許多

3. 這題主要是在考連結串列的觀念, 基本上不是太難

程式碼 (1)：

/**
 * 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 listNodes = new ListNode(0);
    const result = listNodes;
    
    let carry = 0;
    let sum = 0;
    
    while (l1 || l2 || carry > 0) {
        sum = 0;
        
        if (l1) {
            sum += l1.val;
            l1 = l1.next;
        }
        
        if (l2) {
            sum += l2.val;
            l2 = l2.next;
        }
        
        sum += carry;
        carry = sum > 9;
        
        
        listNodes.next = new ListNode(sum%10);
        listNodes = listNodes.next;
    }
    
    return result.next;
    
};

執行成果：

程式碼 (2)：

/**
 * 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 result = null;
    let carry = arguments[2] || 0;
    
    if (l1 || l2) {
        const l1Val = l1 ? l1.val : 0;
        const l2Val = l2 ? l2.val : 0;
        const nextL1 = l1 ? l1.next : null;
        const nextL2 = l2 ? l2.next : null;
        
        const sum = l1Val + l2Val + carry;
        
        result = new ListNode(sum % 10);
        result.next = addTwoNumbers(nextL1, nextL2, sum > 9);
    } else if (carry) {
        result = new ListNode(1);
        result.next = null;
    }
    
    return result;
};

執行成果：

備註:

程式碼(1)是透過 while 方式,

程式碼(2)是透過 recursive 的方式解題, 

執行時間與複雜度都是差不多 O(n),

但程式碼的優雅程度有差別