Add Two Numbers is another common early LeetCode question that gets you working with linked lists in a more hands-on way. The digits of each number are stored in reverse order, and you're asked to add them together just like you would on paper, one digit at a time while carrying over when needed. It's a solid example of how to move through two structures at once while keeping track of shared state. We’ll go through each solution step by step so you can see exactly how it works. The two solutions below are written in Java and you'll find copy-paste versions at the very end.
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.
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.
Solution 1 — Simple Iterative Version (O(n))
This version walks through both linked lists one node at a time. It adds the digits from each list, keeps track of the carry, and builds a new result list as it goes.
Let’s break it down step by step:
class Solution {
This defines the solution class. It’s just the standard structure LeetCode expects.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Here’s the method definition. It takes in two linked lists, l1 and l2, and returns a new linked list that represents their sum.
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
We start by creating a dummy node. It doesn't hold part of the answer. It's there to make list operations easier. The tail variable keeps track of where we are in the result list as we add new digits.
int carry = 0;
We also set up a variable to store the carry from one digit to the next. It starts at 0 and gets updated each time two digits are added.
while (l1 != null || l2 != null || carry != 0) {
This loop keeps going until both lists are fully processed and there’s no carry left. That way, we don’t miss any leftover value after the last digits.
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
We grab the current digit from each list. If either list is already finished, we just use 0 for that side. That avoids needing a lot of extra if-checks.
int sum = val1 + val2 + carry;
carry = sum / 10;
We add both digits along with the carry. Then we update the carry by dividing the sum by 10. For example, if the sum is 15, the carry becomes 1.
tail.next = new ListNode(sum % 10);
tail = tail.next;
We create a new node with the last digit of the sum using sum % 10, and link it to the result list. Then we move the tail pointer forward to keep building the list.
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
If either input list still has more nodes, we move forward to the next one. If not, we leave it alone for the next loop to handle.
}
The loop ends here once all digits and carry have been handled.
return dummyHead.next;
For the last step, we return the list that starts after the dummy node. That’s the full sum of the two input numbers, stored in reverse order just like the inputs.
Time complexity is O(n), where n is the length of the longer list, since each digit is visited once. Space complexity is also O(n) if you count the output list, which most do. But if you only count temporary memory used during the process, it's technically O(1).
Solution 2 — Recursive Strategy (O(n))
This version doesn't use a loop. Instead, it uses recursion to process one digit at a time from each list, while passing the carry along. Each recursive call builds the next part of the result list.
Let’s go through it piece by piece:
class Solution {
This is the class declaration. No changes needed here.
The method addTwoNumbers kicks things off by calling a helper method named add. It passes both input lists along with an initial carry of 0. This sets up the recursion.
private ListNode add(ListNode l1, ListNode l2, int carry) {
The helper method takes in two list nodes and the carry. It's going to return a new node that becomes part of the final result.
This is the stopping point. If both lists are empty and there’s no carry left, we’re done. The method returns null to signal that the recursion can end.
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
We get the current values from both lists. If either list has already ended, we just use 0 for that side. That way, we don’t need to worry about different lengths.
int sum = val1 + val2 + carry;
We add the two digits and the carry from the previous step. This gives us the total for this position.
ListNode node = new ListNode(sum % 10);
We create a new node to hold the last digit of the sum. Using sum % 10 gets us just the rightmost digit. For example, if the sum is 18, this gives us 8.
Here’s the recursive part. We move to the next nodes in both lists, or pass null if we’ve reached the end of either one. We also pass the new carry using sum / 10, which keeps everything in sync for the next digit.
return node;
}
}
We return the current node. As the recursion finishes, each call attaches the next digit to the result, one node at a time.
Time complexity is O(n) as well, with one recursive step for each digit. Space complexity is O(n) too, but in this case it comes from the call stack. Each call adds a new layer until the base case is reached, so the depth of the stack matches the length of the longer list.
Iterative Solution— Copy and Paste
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
tail.next = new ListNode(sum % 10);
tail = tail.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummyHead.next;
}
}
Recursive Solution— Copy and Paste
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return add(l1, l2, 0);
}
private ListNode add(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) return null;
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
node.next = add((l1 != null) ? l1.next : null, (l2 != null) ? l2.next : null, sum / 10);
return node;
}
}
