Add Two Numbers

Problem Statement

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.

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

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

Approach: Elementary Math Simulation

Since the digits in the linked lists are stored in reverse order, the heads of the lists correspond to the least significant digits (the “ones” place). This actually makes things easier! We can simulate elementary addition digit by digit, exactly how you would add two numbers on a piece of paper, moving from the ones place up to the tens, hundreds, etc.

We will use a Dummy Node to easily construct our new resulting linked list.

1. Initialize a dummy node and a tail pointer pointing to it.
2. Initialize a carry variable to 0.
3. Loop as long as l1 is not null, OR l2 is not null, OR carry is greater than 0:
   • Extract the values from the current nodes of l1 and l2. If either list has been fully traversed, treat its missing digit as 0.
   • Calculate the sum of the two digits plus any existing carry: sum = val1 + val2 + carry.
   • Update the carry for the next iteration. It will be the tens digit of the sum: carry = Math.floor(sum / 10).
   • Determine the digit to store in our new node. It will be the ones digit of the sum: digit = sum % 10.
   • Create a new node with this digit, attach it to tail.next, and advance the tail pointer.
   • Advance l1 and l2 to their next nodes (if they aren’t already null).
4. Return dummy.next to get the true head of the newly constructed linked list.

(Note: Including carry > 0 in our loop condition elegantly handles the case where the final addition results in an extra carry digit, e.g., $9 + 9 = 18$, where we need to create a new final node for the 1).

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}
 */
function addTwoNumbers(l1, l2) {
    let dummy = new ListNode(0);
    let tail = dummy;
    let carry = 0;
    
    // Continue if there are nodes left in l1 OR l2 OR if there's a leftover carry
    while (l1 !== null || l2 !== null || carry > 0) {
        // If a list is exhausted, use 0 as the value
        let val1 = (l1 !== null) ? l1.val : 0;
        let val2 = (l2 !== null) ? l2.val : 0;
        
        let sum = val1 + val2 + carry;
        
        // Compute new carry (e.g., 18 / 10 = 1)
        carry = Math.floor(sum / 10);
        
        // Append the ones digit of the sum to the new list (e.g., 18 % 10 = 8)
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        
        // Move to the next nodes
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
    
    return dummy.next;
}

Complexity Analysis

• Time Complexity: $O(\max(m, n))$ where $m$ and $n$ are the lengths of l1 and l2 respectively. We traverse through both lists at most once, and the number of iterations is dictated by the longer list.
• Space Complexity: $O(\max(m, n))$ to store the new resulting linked list. The new list will have a length of at most $\max(m, n) + 1$. (Note: Output space is generally not counted towards auxiliary space complexity in some contexts, meaning this could also be considered $O(1)$ auxiliary space).