Add Two Numbers
Last Updated: March 29, 2026
Understanding the Problem
We have two numbers represented as linked lists where each node holds a single digit, and the digits are stored in reverse order. So the list [2,4,3] represents the number 342. We need to add these two numbers and return the result as a linked list in the same reversed format.
The reverse storage is actually a gift. When you add numbers by hand, you start from the ones digit (the rightmost), then move left. Since the linked lists already start from the least significant digit, we can traverse both lists from head to tail and add digits in the natural order of addition. No reversal needed.
The main challenge is handling the carry. When two digits sum to 10 or more, we need to carry 1 over to the next position. And what happens when the lists are different lengths? We need to keep going with whichever list still has digits. Finally, after processing both lists, there might be a leftover carry that needs its own node (like 999 + 1 = 1000).
Key Constraints:
1 <= list length <= 100→ Both lists have at least one node and at most 100 nodes. With n up to 100, any O(n) approach is more than sufficient.0 <= Node.val <= 9→ Each node holds exactly one digit. The sum of two nodes is at most 18 (9+9), so the carry is always 0 or 1.No leading zeros→ The input is well-formed. The only number with a leading zero is 0 itself (a single node with value 0).
Approach 1: Iterative with Carry
Intuition
Think about how you add two numbers on paper. You start from the rightmost digits, add them together, write down the ones digit, and carry over to the next column. That's exactly what we need to do here, and the reversed linked list format means we're already starting from the rightmost digits.
We traverse both lists simultaneously. At each step, we add the current digits from both lists (if they exist) plus any carry from the previous step. The ones digit of this sum becomes a new node in our result list, and the tens digit becomes the carry for the next step. We keep going until both lists are exhausted and there's no remaining carry.
A useful trick: use a dummy head node for the result list. Without it, you'd need special logic to create the first node. With a dummy head, every node (including the first real one) gets appended the same way. At the end, you just return dummy.next.
The reverse storage order means the head of each list is the least significant digit, which is exactly where addition starts. By maintaining a carry variable, we handle sums that overflow a single digit. The loop condition l1 || l2 || carry elegantly handles all three scenarios: lists of different lengths, and a final carry that extends the result.
The dummy head trick eliminates the need for a special case when creating the first node. Every iteration creates a new node and appends it the same way. This is a standard linked list pattern worth memorizing.
Algorithm
- Create a dummy head node and a
currentpointer pointing to it. - Initialize
carry = 0. - While either list still has nodes OR carry is non-zero:
- Get the value from
l1(or 0 ifl1is exhausted). - Get the value from
l2(or 0 ifl2is exhausted). - Compute
sum = val1 + val2 + carry. - Create a new node with value
sum % 10. - Update
carry = sum / 10. - Advance
l1,l2, andcurrentto their next nodes. - Return
dummy.next.
Example Walkthrough
Code
- Time Complexity: O(max(m, n)). We traverse both lists once. The loop runs for max(m, n) iterations, plus at most one more for a final carry.
- Space Complexity: O(max(m, n)). The result list has at most max(m, n) + 1 nodes. If we don't count the output, we use O(1) additional space.
The iterative approach is already optimal in time, but recursion offers a different way to express the same logic that can be cleaner to reason about.
Approach 2: Recursive
Intuition
The iterative approach works perfectly, but recursion offers a different way to think about the same problem. Adding two linked-list numbers is a recursive operation: add the current digits plus carry to get a node, then recursively solve the rest of the lists with the new carry.
The base case is when both lists are null and carry is 0. The recursive case creates a node for the current digit sum and recurses on the remaining nodes with the updated carry.
Algorithm
- Define a helper function that takes
l1,l2, andcarry. - Base case: if
l1,l2are both null andcarryis 0, return null. - Compute the sum of current values (or 0 if null) plus carry.
- Create a new node with
sum % 10. - Set its next pointer to the recursive call with
l1.next,l2.next, andsum / 10. - Return the new node.
Example Walkthrough
Code
- Time Complexity: O(max(m, n)). Same as iterative. Each digit is processed once, so we make max(m, n) + 1 recursive calls at most.
- Space Complexity: O(max(m, n)). The recursion stack uses O(max(m, n)) space, on top of the O(max(m, n)) for the result list.