Add Two Numbers II — Stack-Based Reverse-Order Addition Explained

Problem Statement#

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

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

Example 1:

Input:  l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Explanation: 7243 + 564 = 7807

Example 2:

Input:  l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Explanation: 243 + 564 = 807

Example 3:

Input:  l1 = [0], l2 = [0]
Output: [0]

Why This Problem Matters#

Add Two Numbers II (LeetCode 445) is the forward-order sibling of LC 2 (Add Two Numbers). Where LC 2 stores digits in reverse (LSB at head), this problem stores them in forward order (MSB at head). This single difference makes the problem substantially harder because addition must happen from the least significant digit — the tail — but you can't traverse backwards in a singly linked list.

Amazon and Google use this problem specifically to see whether candidates reach for the right tool: stacks. A stack reverses access order — pushing all digits onto a stack and then popping gives you the digits from LSB to MSB, exactly what addition needs.

An alternative is to reverse both input lists, apply the LC 2 algorithm, and reverse the result. This also works but requires modifying the inputs (unless you create copies), which the interviewer may flag.

This problem also demonstrates an important engineering principle: when you can't traverse in the direction you need, find a data structure that changes access order. Stacks are the go-to for "process from the end" requirements on forward-linked structures.

The Core Insight#

You need to add digits from tail to head (LSB to MSB), but the lists only support head-to-tail traversal. Use two stacks: traverse l1 pushing all digits onto stack1, traverse l2 pushing all digits onto stack2. Now popping from each stack gives you digits from LSB to MSB.

Build the result list in reverse order: each time you compute a digit, prepend it to the result (set new_node.next = current_head, then update head to the new node). This builds the result in MSB-first order without needing a final reversal.

Visual Dry Run#

Input: l1 = 7 -> 2 -> 4 -> 3 (7243), l2 = 5 -> 6 -> 4 (564)

Expected: 7243 + 564 = 7807 → output 7 -> 8 -> 0 -> 7

After stacking:

• s1 = [7, 2, 4, 3] (top = 3)
• s2 = [5, 6, 4] (top = 4)

Output: 7 -> 8 -> 0 -> 7. Correct.

Solution (Optimal)#

Python#

def addTwoNumbers(l1, l2):
    # Step 1: Push all digits onto stacks
    s1, s2 = [], []
    while l1:
        s1.append(l1.val)
        l1 = l1.next
    while l2:
        s2.append(l2.val)
        l2 = l2.next
 
    carry = 0
    head = None  # will become the head of the result list
 
    # Step 2: Pop and add, building result in reverse order
    while s1 or s2 or carry:
        a = s1.pop() if s1 else 0
        b = s2.pop() if s2 else 0
 
        total = a + b + carry
        carry = total // 10
        digit = total % 10
 
        # Prepend new node — builds the list in correct MSB-first order
        node = ListNode(digit)
        node.next = head
        head = node
 
    return head

Time complexity: O(m + n) — push and pop each digit once.

Space complexity: O(m + n) — two stacks.

JavaScript#

var addTwoNumbers = function(l1, l2) {
    const s1 = [], s2 = [];
 
    while (l1 !== null) { s1.push(l1.val); l1 = l1.next; }
    while (l2 !== null) { s2.push(l2.val); l2 = l2.next; }
 
    let carry = 0;
    let head = null;
 
    while (s1.length > 0 || s2.length > 0 || carry !== 0) {
        const a = s1.length > 0 ? s1.pop() : 0;
        const b = s2.length > 0 ? s2.pop() : 0;
 
        const total = a + b + carry;
        carry = Math.floor(total / 10);
 
        const node = new ListNode(total % 10);
        node.next = head;
        head = node;
    }
 
    return head;
};

Complexity:

Alternative: reverse both lists, add (LC 2 style), reverse result

def addTwoNumbers(l1, l2):
    def reverse(head):
        prev = None
        while head:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt
        return prev
 
    l1 = reverse(l1)
    l2 = reverse(l2)
 
    # ... apply LC 2 algorithm ...
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    while l1 or l2 or carry:
        a = l1.val if l1 else 0
        b = l2.val if l2 else 0
        total = a + b + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
 
    # Reverse result back to MSB-first order
    return reverse(dummy.next)

This is O(m+n) time and O(1) extra space (beyond the output list) — preferred if modifying the inputs is acceptable.

Common Mistakes#

1. Forgetting to include carry in the while loop condition. If the final addition produces a carry (e.g., 999 + 1 = 1000), the stacks are empty but carry = 1. Without or carry, you'd miss the most significant digit.

2. Appending to the end instead of prepending. If you build the result left-to-right by appending, you get the result in LSB-first order (wrong). Prepend (node.next = head; head = node) builds it in MSB-first order correctly.

3. Using a Java Deque as a stack incorrectly. In Java, ArrayDeque serves as a stack. Use push to add (pushes to front) and pop to remove (removes from front). This gives LIFO order. Do not use add/remove which operate on the tail.

4. Not handling unequal list lengths. When one stack is exhausted, use 0 as the digit. The s1.pop() if s1 else 0 pattern handles this.

5. Reversing approach but forgetting to reverse the output. If you reverse both inputs and apply LC 2, the result is in LSB-first order. You must reverse the result to get MSB-first order. Forgetting this final reversal gives the wrong answer.

Interview Tips#

1. Contrast with LC 2: "In LC 2, digits are in reverse order so we can add left-to-right. Here, they're in forward order (MSB first), so we need to process from the tail. I'll use stacks to reverse access order."

2. Explain the prepend trick: "Instead of building the result forward and reversing it, I prepend each new digit — this automatically gives MSB-first order."

3. Offer the reversal alternative: "Another approach is to reverse both input lists, apply the LC 2 algorithm, then reverse the result. Same O(m+n) time, O(1) extra space if we can modify the inputs."

4. Carry at end: Show [9,9] + [1] = [1,0,0]. Stacks empty after 2 iterations, carry = 1, one more iteration creates the leading 1.

5. Java note: In Java interviews, clarify whether Stack<Integer> or Deque<Integer> is preferred. Deque is the modern recommendation.

Follow-up Questions#

Q: If you cannot modify the input lists, which approach do you prefer? The stack approach — it doesn't modify the inputs. The reversal approach requires modifying l1 and l2 (reversing them), which violates the constraint.

Q: Can you solve it in O(1) extra space (ignoring output)? Only if you can modify the inputs: reverse both lists, add using LC 2 logic, reverse the result. This uses O(1) extra space (just pointer variables). The stack approach uses O(m+n).

Q: What if the numbers are very large (10^1000 digits)? Python handles arbitrary-precision integers natively. For Java/C++, you'd need a BigInteger analog or stick with the digit-by-digit approach in this problem.

Q: What if there are leading zeros in the output? The carry propagation algorithm naturally produces no leading zeros in the result (the carry only creates a new node when non-zero).

Q: How would you add K numbers stored as forward linked lists? Use K stacks, pop all simultaneously, accumulate sum + carry. Build result by prepending. O(total digits) time and O(total digits) space.

Key Takeaways#

• Use stacks to reverse digit order: push all digits, then pop to get LSB first — the key insight for forward-stored numbers.
• Prepend each result node (node.next = head; head = node) to build the output in correct MSB-first order without a final reversal.
• The loop condition while s1 or s2 or carry handles unequal lengths and trailing carry.
• Use 0 when a stack is exhausted — just like using 0 when a list is exhausted in LC 2.
• Alternative: reverse both inputs, apply LC 2, reverse result — O(1) extra space if inputs are modifiable.
• Time O(m+n), Space O(m+n) for the stack approach; O(1) extra space for the reversal approach.