yaohwang.com

Problem Overview

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

Key Point: The digits are stored in reverse order, which makes the addition process straightforward – we add from least significant digit to most significant digit, just like manual addition.

Solution 1: Recursive Approach

How It Works

Recursively process each digit pair, passing the carry to the next recursive call:

def addTwoNumbers(self, l1, l2, carry=0):
    if not l1 and not l2 and not carry:
        return None

    total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
    node = ListNode(total % 10)
    node.next = self.addTwoNumbers(l1.next if l1 else None, 
                                    l2.next if l2 else None, 
                                    total // 10)
    return node

Complexity Analysis

• Time Complexity: O(n) – Processes each node once
• Space Complexity: O(n) – Recursion call stack depth equals the length of the longer list

Limitations

• Recursion depth limits: Can fail on very long lists (Python default recursion limit ~1000)
• Memory overhead: Each recursive call adds to the call stack
• Not scalable: Performance degrades with list length due to stack overhead

Solution 2: Iterative Approach (Recommended)

How It Works

Process both lists simultaneously, digit by digit, maintaining a carry value:

while l1 or l2 or carry:
    v1 = l1.val if l1 else 0
    v2 = l2.val if l2 else 0

    total = v1 + v2 + carry
    carry = total // 10

    curr.next = ListNode(total % 10)
    curr = curr.next

Complexity Analysis

• Time Complexity: O(n) – Single pass through both lists, where n is the length of the longer list
• Space Complexity: O(1) – Only using a constant amount of extra space (excluding the output list)

Advantages

• No recursion depth limitations: Works with lists of any length
• Constant space: Only uses O(1) extra memory
• Better performance: No function call overhead
• Production-ready: Recommended for real-world applications

Key Insights

1. Reverse Order Advantage: Storing digits in reverse order makes addition natural – we process from right to left, just like manual addition.

2. Carry Propagation: The carry must be tracked and propagated to the next digit position, similar to how we add numbers by hand.

3. Unequal Length Lists: Handle cases where one list is longer than the other by treating missing nodes as 0.

4. Final Carry: Don’t forget to handle the final carry if it exists (e.g., 9 + 1 = 10 creates a new digit).

Comparison

Takeaway

While both approaches have the same time complexity, the iterative approach is superior for production use:

• Constant space vs linear space (recursive)
• No recursion depth limits – handles lists of any length
• Better performance – avoids function call overhead

The recursive approach is elegant and helps understand the problem structure, but the iterative solution is the practical choice for real-world applications.