[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.
 struct ListNode :
     val
     ListNode next
     ListNode() : val(0), next(None) :
     ListNode(x) : val(x), next(None) :
     ListNode(x, ListNode next) : val(x), next(next) :
/
class Solution:
def addTwoNumbers(self, l1, l2):
    return 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
    sum = carry
    if l1 != None:
        sum += l1.val
    if l2 != None:
        sum += l2.val
    ListNode newNode = ListNode(sum % 10)
    newNode.next = addTwoNumbersHelper(
    (l1.next if             l1 != None  else None,)
    (l2.next if             l2 != None  else None,)
    sum / 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 addTwoNumbersHelper(self, l1, l2, carry):
    # Base case: all digits processed and no carry
    if l1 == None  and  l2 == None  and  carry == 0:
        return None
    # Calculate sum: carry + l1.val + l2.val
    sum = carry
    if (l1 != None) sum += l1.val
    if (l2 != None) sum += l2.val
    # Create new node with ones digit
    ListNode newNode = ListNode(sum % 10)
    # Recursively process next digits
    newNode.next = addTwoNumbersHelper(
    (l1.next if         l1 != None  else None,  # Move to next or null)
    (l2.next if         l2 != None  else None,  # Move to next or null)
    sum / 10                              # Pass carry forward
    )
    return newNode

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(self, 0)
    ListNode 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
    ListNode head = None
    ListNode tail = None
    carry = 0
    while l1 != None  or  l2 != None  or  carry > 0:
        sum = carry
        if l1 != None:
            sum += l1.val
            l1 = l1.next
        if l2 != None:
            sum += l2.val
            l2 = l2.next
        ListNode newNode = ListNode(sum % 10)
        if head == None:
            head = tail = newNode
             else :
            tail.next = newNode
            tail = newNode
        carry = sum / 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

if l1 == None  and  l2 == None  and  carry == 0:
    return None

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

sum = carry
if (l1 != None) sum += l1.val
if (l2 != None) sum += l2.val
digit = sum % 10  # Ones digit
newCarry = sum / 10  # Tens digit (carry)

Null Handling

(l1.next if l1 != 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]`