Problem Link - https://leetcode.com/problems/add-two-numbers/
At first glance, this problem looks like simple addition.
But the catch is that the numbers are stored inside Linked Lists, and each digit is stored in reverse order.
This problem tests:
- Linked List traversal
- Dummy Node usage
- Carry handling
- Simulation of elementary addition
Let's solve it.
Problem Statement
You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each node contains a single digit.
Add the two numbers and return the sum as a linked list.
Example
Input:
l1 = [2,4,3]
l2 = [5,6,4]
Output:
[7,0,8]
Explanation:
342 + 465 = 807
Since digits are stored in reverse order:
7 -> 0 -> 8
Brute Force Approach
A naive approach would be:
- Convert both linked lists into numbers.
- Add them.
- Create a new linked list from the result.
Why Not?
This approach can fail for very large numbers because they may exceed the range of primitive data types.
Interviewers usually expect us to perform addition directly on the linked lists.
Optimal Approach
Intuition
Think exactly like elementary school addition.
For every digit:
digit1 + digit2 + carry
Store:
sum % 10
Carry forward:
sum / 10
Continue until both linked lists are exhausted.
If a carry still remains, create one final node.
Why Does This Work?
Whenever the sum exceeds 9:
17
We write:
7
in the current position and carry:
1
to the next position.
This is exactly how we perform addition on paper.
Dry Run
Input
l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4
Iteration 1
2 + 5 + 0 = 7
Digit = 7
Carry = 0
Result:
7
Iteration 2
4 + 6 + 0 = 10
Digit = 0
Carry = 1
Result:
7 -> 0
Iteration 3
3 + 4 + 1 = 8
Digit = 8
Carry = 0
Result:
7 -> 0 -> 8
Final Answer
7 -> 0 -> 8
which represents:
807
Optimal Java Solution
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
int digit = sum % 10;
carry = sum / 10;
cur.next = new ListNode(digit);
cur = cur.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
}
}
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(max(N, M)) |
| Space Complexity | O(max(N, M)) |
Where:
- N = Length of first linked list
- M = Length of second linked list
Key Interview Takeaway
The important observation is that we never need to convert the linked lists into actual numbers.
Instead, we simulate the same addition process we learned in school:
digit = sum % 10;
carry = sum / 10;
This single idea solves the entire problem elegantly.
This problem is a reminder that many Linked List questions aren't about fancy algorithms—they're about carefully simulating a process while managing pointers correctly.
