Add Two Numbers II: Stack-Based Linked List Addition

Add Two Numbers II is LeetCode 445, rated Medium. You are given two non-empty linked lists representing two non-negative integers. Unlike the original Add Two Numbers problem, the digits are stored in normal order, with the most significant digit at the head. You need to add them and return the sum as a linked list, also in normal order.

For example, 7 -> 2 -> 4 -> 3 represents 7243 and 5 -> 6 -> 4 represents 564. Their sum is 7807, so the output is 7 -> 8 -> 0 -> 7.

The catch: you are not allowed to modify the input lists. And even if you were, reversing them just to add feels like working around the problem rather than solving it.

Why this problem matters

This problem tests whether you can think about data access order. In the original Add Two Numbers, digits come in reverse order, so you can process them left to right and the math works out. Here, the most significant digit comes first, but addition needs to start from the least significant digit. You need a way to access the end of the list first, which is a classic signal that a stack is the right tool.

The key insight

Addition works right to left. Linked lists only give you left-to-right access. Stacks flip the access order.

If you push every digit from both lists onto separate stacks, the least significant digits end up on top. Now you can pop from both stacks simultaneously, add the digits with a carry just like elementary school column addition, and build the result list by prepending each new node to the front.

The prepending trick is what makes this work without reversing at the end. Each time you compute a new digit, you create a node, point it at the current head, and update the head pointer. The result list grows from right to left, matching the order you need.

The solution

def addTwoNumbers(l1, l2):
    stack1, stack2 = [], []

    while l1:
        stack1.append(l1.val)
        l1 = l1.next

    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    carry = 0
    head = None

    while stack1 or stack2 or carry:
        total = carry

        if stack1:
            total += stack1.pop()
        if stack2:
            total += stack2.pop()

        carry = total // 10
        node = ListNode(total % 10)
        node.next = head
        head = node

    return head

Push phase. Walk each list from head to tail, pushing every value onto its respective stack. This takes O(m + n) time and gives you last-in-first-out access to the digits.

Add phase. Pop from both stacks simultaneously, adding the values along with any carry from the previous step. The carry arithmetic is the same as any digit addition problem: total // 10 gives the carry, total % 10 gives the digit.

Build phase. For each computed digit, create a new ListNode and prepend it to the result. node.next = head followed by head = node inserts at the front in O(1). When both stacks are empty and the carry is zero, head points to the complete result.

No dummy node needed. Because you are prepending rather than appending, there is no need for a dummy head. The head variable starts as None and naturally becomes the first real node on the first iteration.

Visual walkthrough

Let's trace through adding 7 -> 2 -> 4 -> 3 (7243) and 5 -> 6 -> 4 (564). Watch how the stacks provide right-to-left access and the result list is built by prepending.

Notice how each pop gives you the next least-significant digit. The result list grows from the tail toward the head, so when the loop finishes, head already points to the most significant digit. No reversal step needed.

Complexity analysis

Time: O(m + n) where m and n are the lengths of the two lists. You traverse each list once to fill the stacks, then pop each element once during addition.

Space: O(m + n) for the two stacks. The output list also takes O(max(m, n)) space, but that is required by the problem.

Edge cases

• Different length lists. 9 -> 9 (99) plus 1 (1) gives 1 -> 0 -> 0 (100). The shorter stack empties first, and you treat missing pops as 0.
• Carry at the very end. 5 plus 5 gives 1 -> 0. The carry from 5 + 5 = 10 produces an extra node. The or carry in the loop condition handles this.
• One list is a single zero. 0 plus 1 -> 2 -> 3 gives 1 -> 2 -> 3. The zero contributes nothing to the sum.
• Both lists same length, no carry. 1 -> 2 -> 3 plus 4 -> 5 -> 6 gives 5 -> 7 -> 9. The simplest case, with stacks emptying at the same time.

The building blocks

This problem combines two core building blocks:

Stack-based order reversal. Push elements onto a stack to reverse their access order. This is the same principle behind evaluating postfix expressions, matching parentheses, and any problem where you need to process elements in the opposite order from how they arrive. The pattern is always the same: traverse forward, push everything, then pop to go backward.

Prepend-to-build linked list construction. Instead of using a dummy head and appending to the tail, you prepend each new node to the front. node.next = head; head = node inserts at the beginning in O(1). This naturally builds the list in reverse order, which is exactly what you want when your computation proceeds from least significant to most significant digit.

From understanding to recall

The logic here is simple once you see it: stacks flip the order, carry arithmetic handles the math, prepending builds the list. But under interview pressure, the details matter. Which variable starts as None? When do you check or carry? How exactly does the prepend work?

These are the kinds of details that slip away if you only read the solution once. Typing it from scratch, repeatedly, is what turns understanding into fluency. Practice it today, again in a few days, and once more next week. After a few reps the stack setup and prepend loop will feel automatic.

Related posts

• Add Two Numbers - The reverse-order version of this problem, where a dummy head and append approach works naturally
• Evaluate Reverse Polish Notation - Another classic stack problem where the stack provides the right access order for evaluation
• Reverse Linked List - The fundamental linked list reversal technique, and an alternative approach to this problem if modification were allowed