26. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

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]

Problem Breakdown:

1. Create a dummy node to simplify list construction. Initialize a carry variable to 0.

• dummy = ListNode()
  curr = dummy
  carry = 0

2. Loop while either list has nodes remaining or there is a carry. Sum the values from both lists (use 0 if a list is exhausted) plus the carry.

• while l1 or l2 or carry:
      val1 = l1.val if l1 else 0
      val2 = l2.val if l2 else 0
      total = val1 + val2 + carry

3. The new digit is total % 10 and the new carry is total // 10. Create a new node with the digit.

•     carry = total // 10
      curr.next = ListNode(total % 10)
      curr = curr.next

4. Advance both list pointers if they are not null.

•     l1 = l1.next if l1 else None
      l2 = l2.next if l2 else None

5. Return dummy.next as the head of the result list.

• return dummy.next

Summary:

Simulate digit-by-digit addition with carry, similar to manual addition. Use a dummy node to build the result list. Process both lists simultaneously, handling different lengths and final carry.

Time and Space Complexity:

Time Complexity: O(max(n, m)) - we iterate through both lists once.

Space Complexity: O(max(n, m)) - the result list has at most max(n, m) + 1 nodes.

Python Solution:

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    curr = dummy
    carry = 0
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

JavaScript Solution:

var addTwoNumbers = function(l1, l2) {
    const dummy = new ListNode();
    let curr = dummy, carry = 0;
    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const total = val1 + val2 + carry;
        carry = Math.floor(total / 10);
        curr.next = new ListNode(total % 10);
        curr = curr.next;
        l1 = l1 ? l1.next : null;
        l2 = l2 ? l2.next : null;
    }
    return dummy.next;
};

Java Solution:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int total = val1 + val2 + carry;
            carry = total / 10;
            curr.next = new ListNode(total % 10);
            curr = curr.next;
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        return dummy.next;
    }
}