Description

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]

---

Solution

Intuition

The problem requires adding two numbers represented as linked lists, where each node contains a single digit and the digits are stored in reverse order. The key insight is to perform digit-by-digit addition while handling carry values, similar to how we perform addition by hand.

Approach

1. Create a dummy head node to simplify the list construction

2. Iterate through both lists simultaneously while there are nodes or carry value

3. For each position:

   • Sum the digits from both lists (if they exist) plus any carry

   • Create a new node with the ones digit (sum % 10)

   • Calculate the carry for the next position using integer division

The expression (sum / 10) | 0 is a JavaScript-specific optimization for integer division:

• The division sum / 10 gives us a floating-point number

• The bitwise OR operator | with 0 forces the result to be a 32-bit integer

• This is faster than Math.floor() and cleaner than Math.trunc()

Complexity

• Time complexity: O(max(m,n)) where m and n are the lengths of the input lists

  • We traverse both lists once, and the length of the result is at most max(m,n) + 1

• Space complexity: O(max(m,n))

  • We create a new linked list to store the sum

  • The length of the new list is at most max(m,n) + 1 due to possible carry in the most significant digit

Code

function addTwoNumbers(first: ListNode | null, second: ListNode | null): ListNode | null {
    let carry = 0;
    const head = new ListNode();
    let current = head;

    while (first || second || carry) {
        // Calculate sum of current digits and carry:
        let sum = carry + (first?.val || 0) + (second?.val || 0);

        // Create new node with ones digit:
        current.next = new ListNode(sum % 10)

        // Calculate carry for next iteration using bitwise OR for integer division:
        carry = (sum / 10) | 0;

        // Move pointers:
        current = current.next
        first = first?.next;
        second = second?.next;
    } 

    return head.next
};

The early returns aren't necessary as the main loop handles null inputs correctly, and removing them improves code readability without affecting performance.