Add Two Numbers II

Medium · Stack · Explanation and code example

Stack

How it works

If we want to avoid modifying the input lists, we can use stacks to reverse the digit order implicitly. Pushing all digits onto stacks gives us access to them in reverse order when we pop.

This approach preserves the original lists while still allowing us to process digits from least significant to most significant. The rest of the logic is identical: add digits with carry and build the result by prepending nodes.

Steps

  1. Push all values from l1 onto stack s1 and all values from l2 onto stack s2.
  2. Initialize head = null and carry = 0.
  3. While either stack is non-empty or carry > 0:
    • Pop values from s1 and s2 (use 0 if a stack is empty).
    • Compute total = v1 + v2 + carry.
    • Create a new node with value total % 10 and prepend it to head.
    • Update carry = total / 10.
  4. Return head.

Complexity

  • Time complexity: O(m + n)
  • Space complexity: O(m + n)

Where m is the length of l1 and n is the length of l2.

Things to watch for

Adding Digits from Head Instead of Tail

Unlike the basic "Add Two Numbers" problem, the digits here are stored most-significant-digit first. Trying to add digits directly from the head without reversing or using a stack produces wrong results since you are adding the wrong place values together.

Forgetting to Handle Lists of Different Lengths

When lists have different lengths, the shorter list needs to be padded conceptually with leading zeros. Failing to align the lists properly before addition causes incorrect results.

Building Result in Wrong Order

After computing digits from least to most significant, the result must be constructed so that the most significant digit is at the head. Appending to the tail instead of prepending creates a reversed result.

Python code example

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        s1, s2 = [], []

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

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

        carry = 0
        head = None

        while s1 or s2 or carry:
            v1 = s1.pop() if s1 else 0
            v2 = s2.pop() if s2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            node = ListNode(total % 10)
            node.next = head
            head = node

        return head

C++ code example

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;

        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }

        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }

        int carry = 0;
        ListNode* head = nullptr;

        while (!s1.empty() || !s2.empty() || carry) {
            int v1 = s1.empty() ? 0 : s1.top(); if (!s1.empty()) s1.pop();
            int v2 = s2.empty() ? 0 : s2.top(); if (!s2.empty()) s2.pop();
            int total = v1 + v2 + carry;
            carry = total / 10;
            ListNode* node = new ListNode(total % 10);
            node->next = head;
            head = node;
        }

        return head;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations