Introduction
In this problem, two non-negative integers are represented as singly linked lists. Each node contains a single digit, and the digits are stored in the same order as the number.
Our task is to add these two numbers and return the resulting number as a linked list.
One important requirement is that the output should not contain leading zeros.
Understanding the Problem
Consider the linked lists:
1 -> 2 -> 3
9 -> 9 -> 9
These represent:
123
999
Their sum is:
1122
The resulting linked list should be:
1 -> 1 -> 2 -> 2
The challenge is that addition starts from the least significant digit, but linked lists store digits from left to right.
Why Direct Traversal Doesn't Work
For normal addition:
123
+ 999
-----
1122
We start from the rightmost digits:
3 + 9
However, in a singly linked list, we can only move forward.
This means we cannot directly process digits from right to left.
Key Observation
If we reverse both linked lists, the least significant digits come to the front.
Example:
1 -> 2 -> 3
becomes:
3 -> 2 -> 1
Now addition becomes straightforward because we can process digits from left to right while maintaining carry.
Approach
The solution consists of four major steps:
Remove leading zeros from both lists.
Reverse both linked lists.
Add corresponding digits while handling carry.
Reverse the result to restore the correct order.
Step 1: Remove Leading Zeros
Input lists may contain leading zeros.
Example:
0 -> 0 -> 1 -> 2 -> 3
represents:
123
Before processing, we skip all leading zeros.
This ensures the output does not contain unnecessary zeros.
Step 2: Reverse Both Lists
Suppose we have:
1 -> 2 -> 3
9 -> 9 -> 9
After reversal:
3 -> 2 -> 1
9 -> 9 -> 9
Now the least significant digits are available first.
Step 3: Perform Addition
Maintain:
carry = 0
For every step:
sum = digit1 + digit2 + carry
New digit:
sum % 10
New carry:
sum / 10
Example:
3 + 9 = 12
Store:
2
Carry:
1
Continue until both lists and carry are exhausted.
Step 4: Reverse the Result
The generated list is in reverse order.
Example:
2 -> 2 -> 1 -> 1
Reverse it:
1 -> 1 -> 2 -> 2
This gives the final answer.
Example Walkthrough
Input
head1 = 1 -> 2 -> 3
head2 = 9 -> 9 -> 9
Reverse
3 -> 2 -> 1
9 -> 9 -> 9
Addition
3 + 9 = 12
digit = 2
carry = 1
2 + 9 + 1 = 12
digit = 2
carry = 1
1 + 9 + 1 = 11
digit = 1
carry = 1
0 + 0 + 1 = 1
digit = 1
carry = 0
Result Before Reversal
2 -> 2 -> 1 -> 1
After Reversal
1 -> 1 -> 2 -> 2
Java Solution
class Solution {
public Node addTwoLists(Node head1, Node head2) {
head1 = removeLeadingZeros(head1);
head2 = removeLeadingZeros(head2);
head1 = reverse(head1);
head2 = reverse(head2);
Node dummy = new Node(0);
Node curr = dummy;
int carry = 0;
while (head1 != null || head2 != null || carry != 0) {
int sum = carry;
if (head1 != null) {
sum += head1.data;
head1 = head1.next;
}
if (head2 != null) {
sum += head2.data;
head2 = head2.next;
}
curr.next = new Node(sum % 10);
curr = curr.next;
carry = sum / 10;
}
Node result = reverse(dummy.next);
return removeLeadingZeros(result);
}
private Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
private Node removeLeadingZeros(Node head) {
while (head != null && head.data == 0 && head.next != null) {
head = head.next;
}
return head;
}
}
Dry Run
Input
63
7
Linked Lists
6 -> 3
7
Reverse
3 -> 6
7
Addition
3 + 7 = 10
digit = 0
carry = 1
6 + 0 + 1 = 7
digit = 7
carry = 0
Result Before Reversal
0 -> 7
After Reversal
7 -> 0
Output
7 -> 0
Complexity Analysis
Time Complexity
O(n + m)
Each list is traversed a constant number of times.
Space Complexity
O(1)
Ignoring the output list, only a few pointers and variables are used.
Key Insight
Since addition naturally proceeds from the least significant digit, reversing the linked lists transforms the problem into the same process used in elementary arithmetic. After reversing, we simply add digits one by one while maintaining carry, build the result, and reverse it back to obtain the final number in the correct order.
Summary
Adding two numbers represented as linked lists becomes challenging because digits are stored from the most significant position to the least significant position. By removing leading zeros, reversing both linked lists, performing digit-by-digit addition with carry handling, and then reversing the result, we can efficiently compute the sum while preserving the required format. This approach runs in O(n + m) time and uses O(1) auxiliary space, making it optimal for large linked lists.