Add Two Numbers

Difficulty: Medium
Topics: Linked List, Math, Recursion
Link: https://leetcode.com/problems/add-two-numbers/

Problem Description

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

1. Problem Deconstruction (500+ words)

Technical Version: Given two singly-linked lists where each node contains a single digit (0-9) representing the digits of non-negative integers in reverse positional notation (least significant digit first), implement an algorithm that:

Computes the arithmetic sum of the two represented numbers
Constructs a new linked list representing the result in identical reverse digit order
Handles carry propagation through sequential digit addition
Maintains time complexity O(max(m,n)) and space complexity O(max(m,n))) where m,n are list lengths
Preserves the non-negative integer representation invariant (no leading zeros except for zero itself)

Beginner Version: Imagine you have two numbers written backwards - like 342 becomes 2→4→3 and 465 becomes 5→6→4. Your job is to add them together digit by digit, starting from the left, carrying over any extra to the next digit, and writing the answer also backwards. If you get 10 or more when adding two digits, you keep the last digit and carry the first digit to the next column.

Mathematical Formulation: Let $L_1 = [d_{1,0}, d_{1,1}, ..., d_{1,m-1}]$ and $L_2 = [d_{2,0}, d_{2,1}, ..., d_{2,n-1}]$ where $d_{i,j} \in \{0,1,...,9\}$ .

The represented numbers are:

N_1 = \sum_{i=0}^{m-1} d_{1,i} \cdot 10^i

N_2 = \sum_{i=0}^{n-1} d_{2,i} \cdot 10^i

We compute:

N_3 = N_1 + N_2 = \sum_{i=0}^{k-1} d_{3,i} \cdot 10^i

Where $k = \max(m,n)$ or $\max(m,n)+1$ if final carry exists, and $d_{3,i} = (d_{1,i} + d_{2,i} + c_{i-1}) \bmod 10$ with $c_i = \lfloor (d_{1,i} + d_{2,i} + c_{i-1}) / 10 \rfloor$ and $c_{-1} = 0$ .

Constraint Analysis:

“Non-empty linked lists”: Eliminates null input checks, ensures at least one iteration
“1-100 nodes”: Rules out conversion to native integers (100 digits → 10¹⁰⁰ exceeds 64-bit), mandates digit-by-digit processing
“Digits 0-9”: Validates input sanitization, ensures base-10 arithmetic
“No leading zeros except 0”: Eliminates edge cases like 0→0→1 (invalid), but allows single 0 node
Hidden edge cases: Lists of different lengths, final carry creating new digit, single zero inputs, maximum length with carry

2. Intuition Scaffolding

Real-World Metaphor: Like adding two multi-digit numbers on a calculator with broken display that only shows one digit at a time from right to left. You must keep the “carry” in your head as you move to the next digit position.

Gaming Analogy: In RPG inventory management, you have two stacks of identical items where each stack’s count is represented in reverse digit order. Combining stacks requires adding digit by digit while handling overflow, much like managing limited slot capacity per digit position.

Math Analogy: This is essentially implementing the elementary school addition algorithm computationally, but with the convenience that the input is already aligned by place value due to reverse ordering, eliminating the need for padding or reversal operations.

Common Pitfalls:

Forgetting final carry: When 999 + 1 = 1000, missing the extra digit
Unequal list handling: Treating null nodes as zero rather than terminating early
Carry propagation errors: Incorrectly resetting or maintaining carry between iterations
Zero result handling: Not properly representing pure zero case
Modifying input lists: Accidentally changing original data instead of creating new list

3. Approach Encyclopedia

Brute Force → Integer Conversion:

# Convert lists to integers, sum, then convert back
def brute_force(l1, l2):
    # O(m+n) conversion each way
    def to_int(node):
        num, place = 0, 1
        while node:
            num += node.val * place
            place *= 10
            node = node.next
        return num
    
    def to_list(num):
        if num == 0: return ListNode(0)
        dummy = ListNode(0)
        curr = dummy
        while num > 0:
            curr.next = ListNode(num % 10)
            num //= 10
            curr = curr.next
        return dummy.next
    
    return to_list(to_int(l1) + to_int(l2))

Complexity Proof: Each conversion traverses m/n nodes (O(m+n)), arithmetic is O(1) for Python big integers but theoretically O(log N) for arbitrary precision. Space: O(max(m,n)) for result.

Optimal → Iterative Digit Processing:

l1: 2 → 4 → 3
l2: 5 → 6 → 4
     ↓   ↓   ↓
carry: 0 → 1 → 0
     ↓   ↓   ↓   ↓
sum:  7 → 0 → 8 → Ø

Time Complexity: Θ(max(m,n)) iterations, each O(1) operations → O(max(m,n))) Space Complexity: O(max(m,n))) for result list, O(1) auxiliary space

4. Code Deep Dive

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)           # Anchor node to simplify edge cases
    current = dummy               # Builder pointer for result list
    carry = 0                     # Propagated overflow between digits
    
    while l1 or l2 or carry:      # Continue while digits OR carry remain
        # Extract current digits (0 if list exhausted)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        # Compute digit sum with carry
        total = val1 + val2 + carry
        carry = total // 10       # Update carry for next iteration
        digit = total % 10        # Current result digit
        
        # Append new node to result
        current.next = ListNode(digit)
        current = current.next
        
        # Advance input pointers if not exhausted
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    
    return dummy.next             # Skip anchor node

Edge Case Mapping:

Example 1 (342+465): Line 8 handles equal lengths, line 12 captures final digit without carry
Example 2 (0+0): while condition fails immediately, returns dummy.next (None) corrected by carry check
Example 3 (9999999+9999): Lines 14-15 handle unequal lengths, carry propagates through empty lists

5. Complexity War Room

Hardware-Aware Analysis: At maximum constraint (100 nodes → 200 bytes pointers + 100 bytes values ≈ 300 bytes), the entire computation fits in L1 cache (typically 32-64KB). Pointer chasing causes ~100 cache misses but sequential access enables prefetching.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(m+n)	O(max(m,n))	9/10	❌ Fails for >64-bit
Recursive	O(max(m,n))	O(max(m,n)))	7/10	⚠️ Stack overflow risk
Iterative	O(max(m,n))	O(max(m,n)))	8/10	✅ Optimal

6. Pro Mode Extras

Variants Section:

Forward Order Storage: Reverse lists first or use stack
Multiple Lists: Heap-based parallel processing
Arbitrary Base: Parameterize base instead of hardcoding 10
Negative Numbers: Two’s complement handling

Interview Cheat Sheet:

Immediately state: “This is digit-by-digit addition with carry propagation”
Complexity: “O(max(m,n)) time, O(max(m,n)) space for result”
Key insight: “Reverse order eliminates alignment problems”
Edge cases: “Final carry, unequal lengths, zero result”
Testing strategy: “Equal/unequal lengths, carry propagation, zero inputs”

#2 - Add Two Numbers