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.

Additional information

• 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.

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]

Brute Force (Convert to Integer)

Intuition

A simple way to solve this is to treat the linked lists as data structures that need to be converted. We can traverse l1 to build the first integer number, traverse l2 to build the second integer number, add them together using standard math, and then convert the result back into a new linked list.

Algorithm

1. Initialize a helper function to convert a Linked List to an integer:

• Traverse the list, maintaining a multiplier (1, 10, 100...).
• Add node.val * multiplier to the total.

2. Convert l1 to num1.
3. Convert l2 to num2.
4. Calculate total = num1 + num2.
5. Convert total back to a Linked List:

• If total is 0, return [0].
• Extract the last digit (total % 10).
• Create a node and attach it to the list.
• Divide total by 10.

6. Return the new head.

def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    def to_int(node):
        val = 0
        multiplier = 1
        curr = node
        while curr:
            val += curr.val * multiplier
            multiplier *= 10
            curr = curr.next
        return val
        
    total = to_int(l1) + to_int(l2)
    
    if total == 0:
        return ListNode(0)
        
    dummy = ListNode(0)
    curr = dummy
    while total > 0:
        digit = total % 10
        curr.next = ListNode(digit)
        curr = curr.next
        total //= 10
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(m + n)

• Reason: We traverse both lists to convert them to integers, and then traverse the digits of the sum to build the new list.

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

• Reason: We store the result as a new linked list.

Elementary Math (Optimal)

Intuition

We can simulate the way we add numbers on paper (column addition). Since the lists are already in reverse order (least significant digit first), we can traverse both lists simultaneously starting from the heads.

At each step, we add the values of the nodes plus any carry from the previous step.
sum = val1 + val2 + carry
new_digit = sum % 10
new_carry = sum // 10

Algorithm

1. Initialize a dummy head node and a curr pointer.
2. Initialize carry = 0.
3. Loop while l1 exists OR l2 exists OR carry is non-zero:

• Get val1: if l1 exists use l1.val, else 0.
• Get val2: if l2 exists use l2.val, else 0.
• Calculate total = val1 + val2 + carry.
• Update carry = total // 10.
• Create a new node with total % 10 and attach it to curr.next.
• Move curr, l1, and l2 forward (if they exist).

4. Return dummy.next.

def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        # New digit
        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        
        # Update pointers
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
        
    return dummy.next

Time & Space Complexity

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

• Reason: We iterate at most the length of the longer list plus one (for a possible final carry).

• Space complexity: O(1)

• Reason: Ignoring the space required for the output list (which is standard practice), we only use constant extra space for pointers and variables.