Add Two Numbers II
Asked at Pinterest
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Pinterest questions → |
How to Think About It
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.
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.
Key insight: push each list's digits onto a stack. Popping gives digits from least to most significant, exactly the order addition needs.
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.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 headFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.