MediumLinked ListMathStackUpdated Sep 2026

445. Add Two Numbers II

Asked at Pinterest

Difficulty

Medium

Time

O(m + n)

Space

O(m + n)

Pattern

Linked List

Companies

1

Problem

You get two linked lists, l1 and l2. Each list stores a non-negative integer, one digit per node, and the most significant digit comes first. For example, the list 7 -> 2 -> 4 -> 3 means the number 7243.

Add the two numbers and return the sum as a new linked list, again with the most significant digit first. Neither input list has leading zeros, except the number 0 itself, which is stored as a single node 0.

Digits must be added from the least significant side, but the lists start at the most significant side. So you need a way to reach the last digits first. A stack is a natural fit: push all digits, then pop them to get the digits in the right order.

Heads are the big digits

l1 = 72437243nullThe head holds 7 (thousands); the tail holds 3 (ones).l2 = 564564nullSame idea: 5 is the hundreds digit, 4 is the onesdigit.
Addition starts at the tail, but the lists give you the head first, so the work runs backwards.

Constraints

  • ●The number of nodes in each list is in the range [1, 100]
  • ●0 <= Node.val <= 9
  • ●Each list represents a number with no leading zeros, except the number 0 itself

Examples

Example 1
Inputl1 = [7,2,4,3], l2 = [5,6,4]
Output[7,8,0,7]
Why7243 + 564 = 7807. Adding from the right: 3+4=7, 4+6=10 so write 0 and carry 1, 2+5+1=8, then 7 alone gives 7. Read top to bottom that is 7, 8, 0, 7.
Example 2
Inputl1 = [2,4,3], l2 = [5,6,4]
Output[8,0,7]
Why243 + 564 = 807. From the right: 3+4=7, 4+6=10 so write 0 carry 1, 2+5+1=8. The result is 8, 0, 7.
Example 3
Inputl1 = [0], l2 = [0]
Output[0]
Why0 + 0 = 0, so the answer is a single node holding 0.

Asked At

1 companies
CompanyDifficulty
PinterestMediumView all Pinterest questions →

How to Think About It

1

In Add Two Numbers I the digits are stored in reverse, so you add head-first. Here the heads are the most significant digits — you need to start from the tails.

2

Option 1: reverse both lists, add as in part I, reverse the result. It works but modifies the input, which interviewers often forbid in the follow-up.

3

Key insight: push each list's digits onto a stack. Popping gives digits from least to most significant, exactly the order addition needs.

4

Build the result by prepending: each new digit node points to the head built so far. That produces most-significant-first order without a final reversal.

5

Walkthrough for 7243 + 564: stacks [7,2,4,3] and [5,6,4]. Pops: 3+4=7, 4+6=10 (digit 0, carry 1), 2+5+1=8, 7+0=7. Prepending gives 7 -> 8 -> 0 -> 7.

Optimal Approach

Step 1: Push every value of l1 onto s1 and of l2 onto s2.
Step 2: carry = 0, head = null.
Step 3: While s1 or s2 or carry:
total = carry + pop(s1, 0) + pop(s2, 0)
Create node total % 10 whose next is head; set head to it.
carry = total // 10
Step 4: Return head.

Time: O(m + n). Space: O(m + n) for the stacks.

Stacks then prepend

s17243← topPush all of l1; the top of the stack is the ones digit3.s2564← topPush all of l2; the top is 4, so both tops line up foraddition.78070123Pop and add: 3+4=7, 4+6=10 (write 0, carry 1),2+5+1=8, 7+0=7. Each digit is prepended, giving 7 -> 8-> 0 -> 7.total = carry + pop(s1) + pop(s2)new node = total % 10, prependedcarry = total // 10
Pop the digits from the back, add with a carry, and push each new digit onto the front of the answer.
ComplexityTime O(m + n)Space O(m + n)We push every node of both lists once and pop each once; the two stacks hold all m + n digits.

What Trips People Up in Real Interviews

1

Converting the lists to integers. Lists can have 100 digits, which overflows 64-bit numbers in most languages.

2

Forgetting the final carry, so 5 + 5 returns 0 instead of 1 -> 0.

3

Reversing the inputs when the interviewer said not to modify them. Ask first, and have the stack approach ready.

4

Appending to the tail and then reversing at the end — correct, but prepending is simpler.

Solution Code

O(m + n) time
def addTwoNumbers(l1, l2):
    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:
        total = carry
        if s1:
            total += s1.pop()
        if s2:
            total += s2.pop()
        head = ListNode(total % 10, head)
        carry = total // 10
    return head

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Add Two Numbers II problem?

Add Two Numbers II adds two numbers stored as linked lists with the most significant digit first, returning the sum as a linked list in the same order. Addition naturally runs from the least significant digit, so the challenge is processing the lists in reverse without (ideally) modifying them.

How do you solve Add Two Numbers II?

The optimal approach runs in O(m + n) time and O(m + n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Add Two Numbers II?

Add Two Numbers II is asked at Pinterest. It is a medium difficulty problem.

What are common mistakes on Add Two Numbers II?
  • Converting the lists to integers. Lists can have 100 digits, which overflows 64-bit numbers in most languages.
  • Forgetting the final carry, so `5 + 5` returns `0` instead of `1 -> 0`.
  • Reversing the inputs when the interviewer said not to modify them. Ask first, and have the stack approach ready.
  • Appending to the tail and then reversing at the end — correct, but prepending is simpler.