Add Two Numbers

Problem

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]

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.

Solution

Approach: Elementary Math with Carry

The key insight is to simulate elementary addition digit by digit, handling the carry at each position. Since digits are stored in reverse order, we can process from head to tail.

Algorithm:

Create a dummy node for the result list
Track carry (initially 0)
While there are digits to process or carry exists:
- Add digits from both lists (if available) plus carry
- Create new node with digit value (sum % 10)
- Update carry (sum // 10)
Return dummy.next

Implementation

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            # Get values (0 if node doesn't exist)
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Calculate sum and new carry
            total = val1 + val2 + carry
            carry = total // 10
            digit = total % 10

            # Create new node
            current.next = ListNode(digit)
            current = current.next

            # Move to next nodes
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

Alternative (More Compact):

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = current = ListNode()
        carry = 0

        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)
            current.next = ListNode(digit)
            current = current.next

        return dummy.next

Complexity Analysis

Time Complexity: O(max(m, n)), where m and n are the lengths of the two lists. We process each digit once.
Space Complexity: O(max(m, n)) for the result list. The result has at most max(m,n) + 1 nodes.

Key Insights

Reverse Order Advantage: The reverse storage order (least significant digit first) perfectly matches how we perform addition - from right to left.
Carry Propagation: The carry from one position affects the next position. We must continue processing even after both lists end if there’s a remaining carry.
Different Lengths: Lists may have different lengths. We handle this by treating missing nodes as having value 0.
Final Carry: If there’s a carry after processing all digits, we need an additional node (e.g., 99 + 1 = 100).
divmod Function: Python’s divmod(total, 10) efficiently computes both the carry and digit in one operation: carry, digit = divmod(total, 10).