2. Add Two Numbers
Asked at Google, Meta, Amazon, Microsoft and 3 more
Difficulty
Medium
Time
O(max(m, n))
Space
O(max(m, n))
Pattern
Linked List
Companies
7
Problem
You get two linked lists. Each list stores a non-negative integer, one digit per node, and the digits are in reverse order — the ones digit is at the head, then the tens, and so on. For example, the list 2 → 4 → 3 stands for the number 342.
Add the two numbers and return the sum as a linked list in the same format: digits reversed, one digit per node.
Because the digits are already reversed, you can add them the way you do on paper: start at the head of both lists (the ones digits), add the two digits plus any carry, write down sum % 10, and pass sum // 10 to the next position. The two lists may have different lengths — when one list ends, treat its missing digits as 0. If a carry is left over after both lists end, add one more node for it.
Reversed digits mean add from the head
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
l1 = [2,4,3], l2 = [5,6,4][7,0,8]l1 = [0], l2 = [0][0]l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9][8,9,9,9,0,0,0,1]Asked At
7 companies| 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 → |
| Bloomberg | Medium | View all Bloomberg 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.
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.
One pass with a carry
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
O(max(m, n)) timeclass 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 runs in O(max(m, n)) time and O(max(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?
Add Two Numbers is asked at Google, Meta, Amazon, Microsoft, Oracle, Uber, Bloomberg. 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.