[Medium] 2. 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 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.

Examples

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]
Explanation: 9999999 + 9999 = 10009998

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.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Number representation: How are numbers represented? (Assumption: Each node contains a single digit, most significant digit is head, least significant is tail - reverse order)
Carry handling: How should we handle carry? (Assumption: If sum of two digits >= 10, carry 1 to next position)
Different lengths: What if lists have different lengths? (Assumption: Treat missing digits as 0 - pad shorter list with zeros)
Leading zeros: Can result have leading zeros? (Assumption: No - per constraints, no leading zeros in input, result shouldn’t have them either)
Return format: Should we return a new list or modify existing? (Assumption: Return new linked list - don’t modify input lists)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to add two numbers represented as linked lists. Let me convert them to integers first.”

Naive Solution: Convert both linked lists to integers, add them, then convert result back to linked list.

Complexity: O(n) time, O(1) space (but may overflow)

Issues:

Integer overflow for large numbers (lists can be up to 100 nodes)
Doesn’t work for very large numbers
Not the intended approach for linked list manipulation
Loses the linked list structure advantage

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I should process digits one by one, maintaining carry. This avoids overflow and works with linked lists naturally.”

Improved Solution: Traverse both lists simultaneously, add corresponding digits along with carry. Create new nodes for result. Handle different list lengths by treating missing digits as 0.

Complexity: O(max(m, n)) time, O(max(m, n)) space

Improvements:

No integer overflow issues
Works with linked list structure
Handles different lengths naturally
Processes digits in correct order

Step 3: Optimized Solution (8 minutes)

Final Optimization: “The digit-by-digit approach is optimal. Let me refine it to handle edge cases and consider recursive alternative.”

Best Solution: Iterative digit-by-digit addition with carry propagation. Can also use recursive approach for elegance, but iterative is more space-efficient.

Key Realizations:

Digit-by-digit addition is the correct approach
Carry propagation is straightforward
O(max(m, n)) time and space is optimal
Both iterative and recursive approaches work well

Solution: Recursive Approach

Time Complexity: O(max(m, n)) where m and n are the lengths of l1 and l2
Space Complexity: O(max(m, n)) due to recursion stack

This solution uses a recursive helper function that processes both lists simultaneously, handling carry propagation naturally through the recursion.

Solution: Recursive Helper

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1, l2):
        return self.addTwoNumbersHelper(l1, l2, 0)

    def addTwoNumbersHelper(self, l1, l2, carry):
        # Base case: if both lists are null and no carry
        if l1 == None and l2 == None and carry == 0:
            return None

        total = carry

        if l1 != None:
            total += l1.val

        if l2 != None:
            total += l2.val

        newNode = ListNode(total % 10)

        newNode.next = self.addTwoNumbersHelper(
            l1.next if l1 != None else None,
            l2.next if l2 != None else None,
            total // 10
        )

        return newNode

How the Algorithm Works

Step-by-Step Example: `l1 = [2,4,3]`, `l2 = [5,6,4]`

Initial Call: addTwoNumbersHelper([2,4,3], [5,6,4], 0)

Step 1: Process first digits
  sum = 0 + 2 + 5 = 7
  newNode = ListNode(7 % 10) = ListNode(7)
  carry = 7 / 10 = 0
  Recursive call: addTwoNumbersHelper([4,3], [6,4], 0)

Step 2: Process second digits
  sum = 0 + 4 + 6 = 10
  newNode = ListNode(10 % 10) = ListNode(0)
  carry = 10 / 10 = 1
  Recursive call: addTwoNumbersHelper([3], [4], 1)

Step 3: Process third digits
  sum = 1 + 3 + 4 = 8
  newNode = ListNode(8 % 10) = ListNode(8)
  carry = 8 / 10 = 0
  Recursive call: addTwoNumbersHelper(null, null, 0)

Step 4: Base case reached
  l1 == null && l2 == null && carry == 0 → return null

Result: [7] -> [0] -> [8] -> null

Visual Representation

l1:  2 -> 4 -> 3 -> null  (represents 342)
l2:  5 -> 6 -> 4 -> null  (represents 465)
     ↓    ↓    ↓
     7    0    8
     ↓    ↓    ↓
Result: 7 -> 0 -> 8 -> null  (represents 807)

Calculation: 342 + 465 = 807

Example with Carry: `l1 = [9,9,9,9,9,9,9]`, `l2 = [9,9,9,9]`

Step 1: 9 + 9 + 0 = 18 → digit=8, carry=1
Step 2: 9 + 9 + 1 = 19 → digit=9, carry=1
Step 3: 9 + 9 + 1 = 19 → digit=9, carry=1
Step 4: 9 + 9 + 1 = 19 → digit=9, carry=1
Step 5: 9 + 0 + 1 = 10 → digit=0, carry=1
Step 6: 9 + 0 + 1 = 10 → digit=0, carry=1
Step 7: 9 + 0 + 1 = 10 → digit=0, carry=1
Step 8: 0 + 0 + 1 = 1 → digit=1, carry=0

Result: [8,9,9,9,0,0,0,1]

Key Insights

Recursive Structure: Each recursive call processes one digit from each list
Carry Propagation: Carry is passed down through recursive calls and handled at each level
Unequal Length Handling: When one list ends, treat missing digits as 0
Base Case: Stop when both lists are null AND carry is 0
Reverse Order: Since digits are stored in reverse, we process from least significant to most significant

Algorithm Breakdown

def add_two_numbers_helper(l1, l2, carry: int):
    if l1 is None and l2 is None and carry == 0:
        return None
    total = carry
    if l1 is not None:
        total += l1.val
    if l2 is not None:
        total += l2.val
    node = ListNode(total % 10)
    node.next = add_two_numbers_helper(
        l1.next if l1 is not None else None,
        l2.next if l2 is not None else None,
        total // 10,
    )
    return node

Edge Cases

Equal length lists: [2,4,3] + [5,6,4] → [7,0,8]
Different length lists: [9,9,9,9] + [9,9] → [8,9,0,0,1]
Carry at end: [9,9] + [1] → [0,0,1]
Single digits: [5] + [5] → [0,1]
Zero inputs: [0] + [0] → [0]
One list longer: [1] + [9,9,9] → [0,0,0,1]

Alternative Approaches

Approach 2: Iterative with Dummy Node

Time Complexity: O(max(m, n))
Space Complexity: O(1) excluding output space

class Solution:
    def addTwoNumbers(self, l1, l2):
        def dummy():
            return ListNode(0)

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

        while l1 != None or l2 != None or carry > 0:
            if l1 != None:
                carry += l1.val
                l1 = l1.next

            if l2 != None:
                carry += l2.val
                l2 = l2.next

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

        return dummy.next

Pros:

O(1) space complexity (no recursion stack)
More efficient for long lists
Easier to understand for some developers

Cons:

Requires dummy node
More verbose

Approach 3: Iterative Without Dummy Node

Time Complexity: O(max(m, n))
Space Complexity: O(1) excluding output space

class Solution:
    def addTwoNumbers(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1

        head = None
        tail = None
        carry = 0

        while l1 != None or l2 != None or carry > 0:
            total = carry

            if l1 != None:
                total += l1.val
                l1 = l1.next

            if l2 != None:
                total += l2.val
                l2 = l2.next

            newNode = ListNode(total % 10)

            if head == None:
                head = tail = newNode
            else:
                tail.next = newNode
                tail = newNode

            carry = total // 10

        return head

Complexity Analysis

Approach	Time	Space	Pros	Cons
Recursive	O(max(m,n))	O(max(m,n))	Elegant, natural carry handling	Stack overflow risk, O(n) space
Iterative (Dummy)	O(max(m,n))	O(1)	Space efficient, clean code	Requires dummy node
Iterative (No Dummy)	O(max(m,n))	O(1)	Space efficient	More edge case handling

Implementation Details

Recursive Base Case

def add_two_numbers_helper(l1, l2, carry: int):
    if l1 is None and l2 is None and carry == 0:
        return None
    # ... compute total, ListNode, recurse

Why all three conditions?

l1 == nullptr && l2 == nullptr: Both lists exhausted
carry == 0: No remaining carry to propagate
If carry > 0, we need to create one more node

Digit Extraction

total = carry
if l1 is not None:
    total += l1.val
if l2 is not None:
    total += l2.val
digit = total % 10
new_carry = total // 10

Null Handling

l1.next if l1 is not None else None

When a list ends, we pass nullptr to indicate no more digits from that list.

Common Mistakes

Forgetting final carry: Not handling carry after both lists end
Wrong base case: Returning too early when carry > 0
Null pointer dereference: Accessing l1->val when l1 is null
Wrong digit calculation: Using sum / 10 instead of sum % 10 for digit
Memory leaks: Not properly managing dynamically allocated nodes

Optimization Tips

Iterative Preferred: For production code, use iterative approach to avoid stack overflow
Dummy Node: Simplifies code by avoiding special cases for head
Early Termination: Can optimize by checking if both lists are null and carry is 0
In-place Modification: Could modify one list in-place to save space (not recommended)

445. Add Two Numbers II - Digits stored in forward order
67. Add Binary - Add binary strings
415. Add Strings - Add number strings
43. Multiply Strings - Multiply number strings
369. Plus One Linked List - Add one to linked list number

Real-World Applications

Big Integer Arithmetic: Handling numbers larger than standard data types
Calculator Implementation: Adding large numbers digit by digit
Cryptography: Modular arithmetic operations
Financial Systems: Precise decimal calculations
Scientific Computing: High-precision arithmetic

Pattern Recognition

This problem demonstrates the “Two Pointers with Carry” pattern:

Process two sequences simultaneously:
  - Handle different lengths gracefully
  - Propagate carry/borrow through iterations
  - Create result on-the-fly

Recursive vs Iterative

When to Use Recursive

Pros:
- More elegant and concise
- Natural carry propagation
- Easier to reason about
Cons:
- O(n) space for recursion stack
- Risk of stack overflow for very long lists
- Slightly slower due to function call overhead

When to Use Iterative

Pros:
- O(1) space complexity
- No stack overflow risk
- Better performance
Cons:
- More verbose code
- Requires careful pointer management

Recommendation: Use iterative approach for production code, recursive for interviews/learning.

This problem is a classic introduction to linked list manipulation and demonstrates how recursion can elegantly handle carry propagation in arithmetic operations.

Robina Li

[Medium] 2. Add Two Numbers

[Medium] 2. Add Two Numbers

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Recursive Approach

Solution: Recursive Helper

How the Algorithm Works

Step-by-Step Example: `l1 = [2,4,3]`, `l2 = [5,6,4]`

Visual Representation

Example with Carry: `l1 = [9,9,9,9,9,9,9]`, `l2 = [9,9,9,9]`

Key Insights

Algorithm Breakdown

Edge Cases

Alternative Approaches

Approach 2: Iterative with Dummy Node

Approach 3: Iterative Without Dummy Node

Complexity Analysis

Implementation Details

Recursive Base Case

Digit Extraction

Null Handling

Common Mistakes

Optimization Tips

Real-World Applications

Pattern Recognition

Recursive vs Iterative

When to Use Recursive

When to Use Iterative

Related Posts

Recent Posts

[Medium] 2. Add Two Numbers

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Recursive Approach

Solution: Recursive Helper

How the Algorithm Works

Step-by-Step Example: l1 = [2,4,3], l2 = [5,6,4]

Visual Representation

Example with Carry: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Key Insights

Algorithm Breakdown

Edge Cases

Alternative Approaches

Approach 2: Iterative with Dummy Node

Approach 3: Iterative Without Dummy Node

Complexity Analysis

Implementation Details

Recursive Base Case

Digit Extraction

Null Handling

Common Mistakes

Optimization Tips

Related Problems

Real-World Applications

Pattern Recognition

Recursive vs Iterative

When to Use Recursive

When to Use Iterative

Related Posts

Recent Posts

Step-by-Step Example: `l1 = [2,4,3]`, `l2 = [5,6,4]`

Example with Carry: `l1 = [9,9,9,9,9,9,9]`, `l2 = [9,9,9,9]`