Add Two Numbers

Difficulty: Medium | Acceptance: 46.79% | Paid: No

Topics: Linked List, Math, Recursion

• Examples
• Constraints
• Brute Force Approach
• Optimal Approach
• Recursive Approach

Examples

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]

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. 

Brute Force Approach

Intuition

Simulate the addition process exactly as we do manually, starting from the least significant digit (head of the lists). Handle carries properly and build the result list node by node.

Steps

• Traverse both linked lists simultaneously.
• At each step, sum the corresponding digits and the carry from the previous step.
• Create a new node with the digit value of the sum (sum % 10) and update the carry (sum // 10).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy_head = ListNode(0)
    current = dummy_head
    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
        digit = total % 10
        
        current.next = ListNode(digit)
        current = current.next
        
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    
    return dummy_head.next

Complexity

• Time: O(max(m, n)) where m and n are the lengths of the two lists
• Space: O(max(m, n)) for the result list
• Notes: The algorithm traverses each list at most once. The space is for the output list which can be at most max(m,n)+1 in length.

Optimal Approach

Intuition

The brute force approach is already optimal in terms of time complexity. We can make minor optimizations to reduce constant factors such as avoiding conditional checks inside the loop when possible.

Steps

• Same as brute force but optimize implementation details.
• Reuse one of the existing lists to avoid allocation of new nodes where possible.
• Minimize conditional checks inside the loop body.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0
    
    while l1 or l2:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        total = val1 + val2 + carry
        carry, digit = divmod(total, 10)
        
        current.next = ListNode(digit)
        current = current.next
        
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    
    if carry:
        current.next = ListNode(carry)
    
    return dummy_head.next

Complexity

• Time: O(max(m, n))
• Space: O(max(m, n))
• Notes: This approach is already asymptotically optimal. The optimization is in implementation details, not in algorithmic complexity.

Recursive Approach

Intuition

The problem can be solved recursively by handling one digit at a time and passing the carry to the next recursive call. This naturally follows the structure of the linked lists.

Steps

• Create a recursive helper function that takes the current nodes and carry.
• Base case: when both nodes are null and carry is 0.
• Recursive case: compute sum, create node for current digit, and recurse on next nodes with new carry.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    def addHelper(n1, n2, carry):
        if not n1 and not n2 and carry == 0:
            return None
        
        val1 = n1.val if n1 else 0
        val2 = n2.val if n2 else 0
        
        total = val1 + val2 + carry
        new_carry, digit = divmod(total, 10)
        
        node = ListNode(digit)
        node.next = addHelper(
            n1.next if n1 else None,
            n2.next if n2 else None,
            new_carry
        )
        
        return node
    
    return addHelper(l1, l2, 0)

Complexity

• Time: O(max(m, n))
• Space: O(max(m, n)) due to recursion stack
• Notes: The recursive approach has the same time complexity but uses additional space for the call stack. It’s elegant but may cause stack overflow for very long lists.