92. Add Two Numbers
🔗 LeetCode Problem: 2. Add Two Numbers
📊 Difficulty: Medium
🏷️ Topics: Linked List, Math, Recursion
Problem Statement
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
Visual:
2 → 4 → 3 (represents 342)
5 → 6 → 4 (represents 465)
___________
7 → 0 → 8 (represents 807)
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: 9999999 + 9999 = 10009998
Visual:
9 → 9 → 9 → 9 → 9 → 9 → 9
9 → 9 → 9 → 9
_________________________
8 → 9 → 9 → 9 → 0 → 0 → 0 → 1
(Note the carry propagates all the way!)
Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
🌟 ELI5: The Simple Idea!
Think of adding numbers by hand:
How we add 342 + 465:
3 4 2
+ 4 6 5
_______
Start from RIGHT (ones place):
2 + 5 = 7, write 7, carry 0
Tens place:
4 + 6 = 10, write 0, carry 1
Hundreds place:
3 + 4 + 1(carry) = 8, write 8, carry 0
Result: 807 ✓
In this problem, numbers are ALREADY reversed!
[2,4,3] means: 2 is ones, 4 is tens, 3 is hundreds
So we can add from LEFT to RIGHT!
No need to reverse!
Position: 1st 2nd 3rd
↓ ↓ ↓
l1: 2 → 4 → 3 (342)
l2: 5 → 6 → 4 (465)
Add: 7 0 8
Carry: 0 1 0
Key Insight: Just like elementary school addition! - Add corresponding digits - Track the carry - Create new digit node - Handle carry at the end
🎨 Visual Understanding
The Addition Process
Example: [2,4,3] + [5,6,4] = 342 + 465
Step 1: Add first digits
2 + 5 = 7
carry = 0
Create node: 7
Result: 7 → ?
Step 2: Add second digits
4 + 6 = 10
10 % 10 = 0 (digit)
10 / 10 = 1 (carry)
Create node: 0
Result: 7 → 0 → ?
Step 3: Add third digits + carry
3 + 4 + 1 = 8
8 % 10 = 8 (digit)
8 / 10 = 0 (carry)
Create node: 8
Result: 7 → 0 → 8 → ?
Step 4: Both lists empty, carry = 0
Done!
Final: 7 → 0 → 8 (represents 807) ✓
Example with Different Lengths
Example: [9,9,9,9] + [9,9]
Position: 1st 2nd 3rd 4th 5th
↓ ↓ ↓ ↓ ↓
l1: 9 → 9 → 9 → 9 → null
l2: 9 → 9 → null
Add: 8 9 0 0 1
Carry: 1 1 1 1 0
Step-by-step:
9 + 9 = 18 → digit=8, carry=1
9 + 9 + 1 = 19 → digit=9, carry=1
9 + 0 + 1 = 10 → digit=0, carry=1 (l2 is null, treat as 0)
9 + 0 + 1 = 10 → digit=0, carry=1
0 + 0 + 1 = 1 → digit=1, carry=0 (both null, but carry exists!)
Result: 8 → 9 → 0 → 0 → 1 ✓
🎯 Approach 1: Iterative with Dummy Node ⭐
The Optimal Solution
Algorithm:
1. Create dummy node to build result
2. Track carry (starts at 0)
3. While either list has nodes OR carry exists:
- Get values (0 if list is null)
- Add: sum = val1 + val2 + carry
- Create new node: sum % 10
- Update carry: sum / 10
- Move all pointers forward
4. Return dummy.next
Implementation
/**
* Iterative addition with carry tracking
* Time: O(max(m,n)), Space: O(max(m,n))
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
// Continue while either list has nodes OR carry exists
while (l1 != null || l2 != null || carry != 0) {
// Get values (0 if null)
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
// Calculate sum
int sum = val1 + val2 + carry;
// Create new digit node
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
// Move pointers forward
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
⏰ Time: O(max(m, n)) where m and n are lengths of the two lists
💾 Space: O(max(m, n)) for the result list (not counting output)
🔍 Super Detailed Dry Run
Example: l1 = [2,4,3], l2 = [5,6,4]
Goal: Add 342 + 465 = 807
Initial state:
l1 → 2 → 4 → 3 → null
l2 → 5 → 6 → 4 → null
dummy → null
current = dummy
carry = 0
═══════════════════════════════════════════════════════════════
Iteration 1: Add first digits
═══════════════════════════════════════════════════════════════
Condition: l1 != null (2) || l2 != null (5) || carry != 0 (0) ✓
Get values:
val1 = l1.val = 2
val2 = l2.val = 5
Calculate:
sum = val1 + val2 + carry
sum = 2 + 5 + 0 = 7
carry = sum / 10 = 7 / 10 = 0
digit = sum % 10 = 7 % 10 = 7
Create node:
current.next = new ListNode(7)
dummy → 7 → null
current = current.next
current points to node 7
Move pointers:
l1 = l1.next → 4 → 3 → null
l2 = l2.next → 6 → 4 → null
State after iteration 1:
Result: dummy → 7 → ?
carry = 0
l1 at: 4
l2 at: 6
═══════════════════════════════════════════════════════════════
Iteration 2: Add second digits
═══════════════════════════════════════════════════════════════
Condition: l1 != null (4) || l2 != null (6) || carry != 0 (0) ✓
Get values:
val1 = l1.val = 4
val2 = l2.val = 6
Calculate:
sum = val1 + val2 + carry
sum = 4 + 6 + 0 = 10
carry = sum / 10 = 10 / 10 = 1
digit = sum % 10 = 10 % 10 = 0
Create node:
current.next = new ListNode(0)
dummy → 7 → 0 → null
current = current.next
current points to node 0
Move pointers:
l1 = l1.next → 3 → null
l2 = l2.next → 4 → null
State after iteration 2:
Result: dummy → 7 → 0 → ?
carry = 1 (important!)
l1 at: 3
l2 at: 4
═══════════════════════════════════════════════════════════════
Iteration 3: Add third digits + carry
═══════════════════════════════════════════════════════════════
Condition: l1 != null (3) || l2 != null (4) || carry != 0 (1) ✓
Get values:
val1 = l1.val = 3
val2 = l2.val = 4
Calculate:
sum = val1 + val2 + carry
sum = 3 + 4 + 1 = 8
carry = sum / 10 = 8 / 10 = 0
digit = sum % 10 = 8 % 10 = 8
Create node:
current.next = new ListNode(8)
dummy → 7 → 0 → 8 → null
current = current.next
current points to node 8
Move pointers:
l1 = l1.next → null
l2 = l2.next → null
State after iteration 3:
Result: dummy → 7 → 0 → 8 → ?
carry = 0
l1 at: null
l2 at: null
═══════════════════════════════════════════════════════════════
Iteration 4: Check loop condition
═══════════════════════════════════════════════════════════════
Condition: l1 != null (null) || l2 != null (null) || carry != 0 (0) ✗
All false, exit loop!
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return: dummy.next
Final list: 7 → 0 → 8 → null ✓
Represents: 807
Result: [7, 0, 8]
Example 2: With carry at end - [9,9,9,9] + [9,9,9,9]
Both: 9999 + 9999 = 19998
Process:
9 + 9 + 0 = 18 → digit=8, carry=1
9 + 9 + 1 = 19 → digit=9, carry=1
9 + 9 + 1 = 19 → digit=9, carry=1
9 + 9 + 1 = 19 → digit=9, carry=1
Both lists null, but carry = 1!
Loop continues because carry != 0:
0 + 0 + 1 = 1 → digit=1, carry=0
Result: 8 → 9 → 9 → 9 → 1 ✓
Represents: 19998
🎯 Approach 2: Recursive ⭐
Elegant Recursive Solution
/**
* Recursive addition
* Time: O(max(m,n)), Space: O(max(m,n))
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addWithCarry(l1, l2, 0);
}
private ListNode addWithCarry(ListNode l1, ListNode l2, int carry) {
// Base case: both null and no carry
if (l1 == null && l2 == null && carry == 0) {
return null;
}
// Get values
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
// Calculate sum
int sum = val1 + val2 + carry;
// Create current node
ListNode result = new ListNode(sum % 10);
// Recursively calculate next
ListNode next1 = (l1 != null) ? l1.next : null;
ListNode next2 = (l2 != null) ? l2.next : null;
result.next = addWithCarry(next1, next2, sum / 10);
return result;
}
⏰ Time: O(max(m, n))
💾 Space: O(max(m, n)) - Recursion stack + result
🎯 Key Insights
Insight 1: The Loop Condition
// ⚠️ CRITICAL: Three conditions!
while (l1 != null || l2 != null || carry != 0) {
// ...
}
Why all three?
l1 != null → Still have digits in l1
l2 != null → Still have digits in l2
carry != 0 → Have carry to propagate!
Example where carry matters:
[5] + [5] = [0, 1]
5 + 5 = 10
After first iteration: l1=null, l2=null, carry=1
Must continue to create node 1!
Insight 2: Handle Null Lists
// When one list is shorter, treat as 0
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
Example:
[9,9] + [1]
Position 1: 9 + 1 = 10 → 0, carry=1
Position 2: 9 + 0 + 1 = 10 → 0, carry=1 (l2 is null, use 0!)
Position 3: 0 + 0 + 1 = 1 → 1, carry=0
Result: [0, 0, 1] ✓
Insight 3: Carry Calculation
// Two operations for carry
int sum = val1 + val2 + carry;
carry = sum / 10; // Next carry (integer division)
digit = sum % 10; // Current digit (modulo)
Examples:
sum = 7 → carry=0, digit=7
sum = 10 → carry=1, digit=0
sum = 18 → carry=1, digit=8
sum = 27 → carry=2, digit=7 (can happen with large carry!)
⚠️ Common Mistakes
Mistake 1: Forgetting carry in loop condition
// ❌ WRONG - Misses final carry!
while (l1 != null || l2 != null) {
// What if carry exists at end?
}
// Example: [5] + [5]
// After loop: result is [0], missing the carry 1!
// ✓ CORRECT - Include carry
while (l1 != null || l2 != null || carry != 0) {
// Handles final carry!
}
Mistake 2: Not handling null lists
// ❌ WRONG - Crashes when one list ends!
int sum = l1.val + l2.val + carry; // NullPointerException!
// ✓ CORRECT - Check for null
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
Mistake 3: Moving null pointers
// ❌ WRONG - Can't call .next on null!
l1 = l1.next; // Crashes if l1 is null!
l2 = l2.next;
// ✓ CORRECT - Check before moving
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
Mistake 4: Creating nodes incorrectly
// ❌ WRONG - Using sum directly
current.next = new ListNode(sum); // Can be > 9!
// ✓ CORRECT - Use modulo
current.next = new ListNode(sum % 10);
Mistake 5: Forgetting to move current
// ❌ WRONG - Overwrites same position!
while (...) {
current.next = new ListNode(sum % 10);
// Forgot: current = current.next;
}
// ✓ CORRECT - Move current forward
current.next = new ListNode(sum % 10);
current = current.next;
🎯 Pattern Recognition
Problem Type: Digit-by-Digit Arithmetic on Linked Lists
Core Pattern: Parallel Traversal + Carry Tracking
When to Apply:
✓ Add numbers as linked lists
✓ Subtract numbers as lists
✓ Multiply numbers as lists
✓ Digit-by-digit operations
✓ Numbers in reverse order
Recognition Keywords:
- "add two numbers"
- "digits"
- "reverse order"
- "linked list"
- "carry"
Similar Problems:
- Add Two Numbers II (LC 445) - Numbers NOT reversed
- Plus One Linked List (LC 369) - Add 1 to number
- Multiply Strings (LC 43) - Similar carry logic
- Add Binary (LC 67) - Same pattern, binary
Key Components:
┌────────────────────────────────────────────┐
│ Dummy Node: Build result list │
│ Carry: Track overflow between digits │
│ Loop: While lists OR carry exists │
│ Handle Null: Treat as 0 │
│ Time: O(max(m,n)), Space: O(max(m,n)) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I see this is digit-by-digit addition"
Step 2: "Numbers are already reversed, so I can add left to right"
Step 3: "I'll track carry and handle different lengths"
Step 4: "Must continue if carry exists at end"
Key Points to Mention:
- Reverse order simplifies addition
- Three-condition loop (l1, l2, carry)
- Treat null as 0 for shorter lists
- Carry can exist after both lists end
- Create new nodes (don't modify input)
- Time: O(max(m,n)), Space: O(max(m,n))
Walk Through Example:
"For [2,4,3] + [5,6,4]:
Start with carry=0.
Add 2+5+0=7, digit 7, carry 0.
Add 4+6+0=10, digit 0, carry 1.
Add 3+4+1=8, digit 8, carry 0.
Both lists empty, carry 0, done.
Result: [7,0,8] representing 807."
Edge Cases to Mention:
✓ Different lengths → handle with 0
✓ Final carry → loop continues
✓ All 9's → maximum carry propagation
✓ Single digits → works correctly
📝 Quick Revision Notes
🎯 Core Concept:
Add Two Numbers: Numbers in reverse order - add from left to right! Use dummy node to build result. Track carry throughout. Loop while l1 OR l2 OR carry exists. Treat null as 0. Sum = val1 + val2 + carry. Digit = sum % 10, Carry = sum / 10.
⚡ Quick Implementation:
class Solution {
public static ListNode create(List<Integer> list) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
for(int num : list) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
int carry = 0;
int digit = 0;
while (l1 != null || l2 != null || carry != 0) {
int num1 = l1 == null ? 0 : l1.val;
int num2 = l2 == null ? 0 : l2.val;
int sum = num1 + num2 + carry;
digit = sum % 10;
carry = sum / 10;
curr.next = new ListNode(digit);
l1 = l1 == null ? l1 : l1.next;
l2 = l2 == null ? l2 : l2.next;
curr = curr.next;
}
return dummy.next;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(2,4,3));
ListNode list2 = create(Arrays.asList(5,6,4));
print(t.addTwoNumbers(list1, list2));
print(t.addTwoNumbers(create(Arrays.asList(0)), create(Arrays.asList(0))));
print(t.addTwoNumbers(create(Arrays.asList(9,9,9,9,9,9,9)), create(Arrays.asList(9,9,9,9))));
}
}
🔑 Key Insights:
- Pattern: Parallel Traversal + Carry
- Loop: THREE conditions (l1, l2, carry)
- Null Handling: Treat as 0
- Carry: sum / 10 (next), sum % 10 (current)
- Final Carry: Loop continues for it!
- Time: O(max(m,n)), Space: O(max(m,n)) ✓
🎪 Memory Aid:
"Elementary school addition: digit + digit + carry!"
"Loop while ANY exists: l1, l2, or carry!" ✨
⚠️ Critical Loop Condition:
while (l1 != null || l2 != null || carry != 0)
↑ ↑ ↑
Has l1 Has l2 Has carry
Example: [5] + [5]
5 + 5 = 10
After: l1=null, l2=null, carry=1
Must continue! Create node 1!
Result: [0, 1] ✓ (not just [0])
🧪 Edge Cases
Case 1: Different lengths
Input: l1 = [9,9], l2 = [1]
Output: [0,0,1]
Handled: Treat missing as 0
Case 2: Final carry
Input: l1 = [5], l2 = [5]
Output: [0,1]
Handled: Loop continues for carry
Case 3: All 9's
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Handled: Carry propagates correctly
Case 4: Zero
Input: l1 = [0], l2 = [0]
Output: [0]
Handled: Works correctly
Case 5: Single digit each
Input: l1 = [2], l2 = [3]
Output: [5]
Handled: No carry needed
All handled perfectly! ✓
Related Problems
- Add Two Numbers II (LC 445) - Numbers NOT reversed
- Plus One Linked List (LC 369) - Add 1
- Multiply Two Numbers (LC 371) - Related concept
- Add Binary (LC 67) - Same pattern, binary strings
Happy practicing! 🎯
Note: This problem teaches the carry propagation pattern used in many arithmetic problems! The three-condition loop (l1 || l2 || carry) is the key insight. Master this and you'll handle all digit-based arithmetic problems with ease! 💪✨