2 - Add Two Numbers

Difficulty: Medium | Pattern: Linked List Simulation | Company tags: Amazon, Microsoft, Facebook, Bloomberg

Problem Statement

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 have leading zeros, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807 (reversed: 7,0,8)

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]

Approach: Digit-by-Digit with Carry — O(max(m,n))

Key insight: Simulate grade-school addition. Process both lists simultaneously, maintaining a carry. Create a new node for each digit of the result.

Algorithm Flow

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    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
        curr.next = ListNode(total % 10)
        curr = curr.next
        
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    
    return dummy.next

Dry Run

l1 = [2,4,3] (342), l2 = [5,6,4] (465)

l1.val	l2.val	carry_in	total	digit	carry_out
2	5	0	7	7	0
4	6	0	10	0	1
3	4	1	8	8	0

Result: [7,0,8] = 807 ✓

Edge Cases

• Different lengths: pad shorter with 0 (handled by val1 = l1.val if l1 else 0)
• Final carry: while ... or carry handles extra carry digit
• Both single nodes: simple addition

Complexity

• Time: O(max(m, n)) where m, n are lengths of l1, l2
• Space: O(max(m, n) + 1) for result list

Key Terms

Term	Definition
Linked list traversal	Walking both lists node by node with pointers l1/l2 until both are exhausted.
Carry propagation	Tracking the overflow digit (total // 10) from one column of addition into the next, just like grade-school arithmetic.
Dummy head node	A placeholder node (dummy = ListNode(0)) that simplifies list-building by avoiding special-casing the first real node.
Reverse-order representation	Storing the least significant digit first, which lets addition proceed left-to-right through the lists exactly like column addition.

FAQ

Q: Why store digits in reverse order instead of normal order? A: Reverse order lets you add starting from the least significant digit without first reversing either list, mirroring how addition naturally carries from right to left.

Q: What happens when the lists have different lengths? A: The val1 = l1.val if l1 else 0 / val2 = l2.val if l2 else 0 pattern treats a missing node as digit 0, so shorter lists are implicitly zero-padded.

Q: Why does the loop condition include or carry? A: If both lists are exhausted but a carry remains (e.g., 999 + 1), you still need one more node for that final carry digit — otherwise the result is truncated.

Q: How would this differ if digits were stored in forward order instead? A: You'd need to reverse both lists first (or use recursion/stacks to process from the tail), add with carry, then reverse the result — turning an O(n) single pass into extra O(n) reversal work.

Q: What's the typical follow-up interviewers ask? A: "Add Two Numbers II" — solve it when digits are stored in forward order without reversing the input lists (typically using stacks).

Quick Revision

• Digits are stored least-significant-first, so addition proceeds naturally from head to tail.
• Use a dummy head node to simplify result-list construction.
• Track carry across iterations; new digit = (val1 + val2 + carry) % 10, new carry = ... // 10.
• Loop while l1 or l2 or carry — this correctly handles unequal lengths and a trailing carry.
• Missing nodes contribute 0 to the sum.
• Build the result by appending one new node per iteration and advancing curr.
• Return dummy.next (skip the placeholder head).
• Time: O(max(m, n)); Space: O(max(m, n) + 1) for the output list.

Related Problems

• "Add Two Numbers II" — same problem but digits stored in forward order (most significant digit first).
• "Add Binary" — same carry-propagation idea applied to binary string addition instead of linked-list digits.
• "Multiply Strings" — extends digit-by-digit simulation with carry to multiplication.