Add Two Numbers
Asked at Google, Meta, Amazon, Microsoft, Oracle, Uber
Problem
You are given two non-empty linked lists representing two non-negative integers stored in reverse order. Add the two numbers and return the sum as a linked list. This problem tests your ability to handle carry propagation and edge cases.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
The numbers are stored in reverse order, which is convenient — you can add from least significant digit to most significant, just like manual addition. No need to reverse anything.
Walk through both lists simultaneously, adding corresponding digits plus carry. The result digit is sum % 10, and the new carry is sum // 10. This is exactly how you add numbers on paper.
Lists can be different lengths. When one list runs out, treat its value as 0. For example: (2 → 4 → 3) + (5 → 6 → 4 → 1) becomes 342 + 1465 = 1807 → (7 → 0 → 8 → 1).
Don't forget the final carry! If both lists end and carry is still non-zero, you need one more node. Example: 5 + 5 = 10 → (0 → 1).
Use a dummy head node to avoid special-casing the first node. The dummy node's next pointer always points to the result list. Return dummy.next at the end.
Visual walkthrough for (2→4→3) + (5→6→4):
2 + 5 = 7, carry=0. Result: 7
4 + 6 = 10, carry=1. Result: 7→0
3 + 4 + 1 = 8, carry=0. Result: 7→0→8
Both lists done, carry=0. Done.
Result: 7→0→8 (represents 807 = 342 + 465)
Optimal Approach
Step 1: Create a dummy head node and a tail pointer.
Step 2: Initialize carry = 0.
Step 3: While l1 or l2 or carry:
- Get values: v1 = l1.val (or 0 if l1 is null), v2 = l2.val (or 0 if l2 is null)
- Calculate total = v1 + v2 + carry
- New digit = total % 10, new carry = total // 10
- Create new node with the digit, append to tail
- Advance l1 and l2 if not
null
Step 4: Return dummy.next.
The dummy head eliminates the "is this the first node?" check. Every node is appended the same way.
Time: O(max(m,n)) — traverse the longer list. Space: O(max(m,n)) for the result list.
What Trips People Up in Real Interviews
Forgetting to handle the carry. When adding two digits plus carry, the result might be >= 10. Always propagate the carry to the next position.
Confusing "reverse order" with "reverse the result." The input is already in reverse order (least significant digit first). You add from left to right, which is correct.
Not handling different list lengths. One list might be longer than the other. When one list is exhausted, treat its value as 0.
Forgetting the final carry. After the loop, if carry > 0, append a new node with the carry value.
Creating a dummy node but forgetting to return dummy.next. The dummy node is a sentinel — return dummy.next to get the actual result head, not the sentinel itself.
Solution Code
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
dummy = ListNode()
curr = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.nextFrequently Asked Questions
What is the Add Two Numbers problem?
You are given two non-empty linked lists representing two non-negative integers stored in reverse order. Add the two numbers and return the sum as a linked list. This problem tests your ability to handle carry propagation and edge cases.
How do you solve Add Two Numbers?
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?
Add Two Numbers is asked at Google, Meta, Amazon, Microsoft, Oracle, Uber. It is a medium difficulty problem.
What are common mistakes on Add Two Numbers?
- Forgetting to handle the carry. When adding two digits plus carry, the result might be >= 10. Always propagate the carry to the next position.
- Confusing "reverse order" with "reverse the result." The input is already in reverse order (least significant digit first). You add from left to right, which is correct.
- Not handling different list lengths. One list might be longer than the other. When one list is exhausted, treat its value as 0.
- Forgetting the final carry. After the loop, if carry > 0, append a new node with the carry value.
- Creating a dummy node but forgetting to return dummy.next. The dummy node is a sentinel — return dummy.next to get the actual result head, not the sentinel itself.