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.
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]
Constraints:
[1, 100].0 <= Node.val <= 9Problem Overview: Two non-empty linked lists represent integers where each node stores a single digit and digits appear in reverse order. Add the two numbers and return the result as a new linked list in the same reversed format.
Approach 1: Iterative Digit-by-Digit Addition (O(n) time, O(1) space)
This approach simulates how you add numbers by hand. Traverse both linked lists at the same time, add corresponding digits, and maintain a carry value for sums greater than 9. For every step, compute sum = val1 + val2 + carry, create a node with sum % 10, and update carry = sum / 10. Continue until both lists are exhausted and the carry becomes zero. This uses simple pointer iteration over a linked list and constant extra memory, making it the most practical and commonly expected solution.
The key insight: because digits are already stored in reverse order, addition naturally proceeds from the least significant digit to the most significant digit. No reversal or extra preprocessing is required. The algorithm only maintains three pointers (l1, l2, result pointer) plus a carry variable, so the extra space is O(1) excluding the output list.
Approach 2: Recursive Addition (O(n) time, O(n) space)
The recursive approach performs the same digit addition but uses the call stack to move through the lists. At each recursive step, read the current digits, compute the sum with carry, create a node with sum % 10, and pass the next nodes and updated carry into the next recursive call. The recursion stops when both lists are null and the carry is zero.
This solution expresses the logic elegantly and mirrors the mathematical process of addition. However, recursion introduces O(n) stack space because each node creates a new call frame. For large inputs, the iterative approach is more memory efficient. Still, recursion can be a clean demonstration of problem decomposition and works well when discussing recursion patterns applied to math-style digit operations.
Recommended for interviews: The iterative carry simulation is the standard answer interviewers expect. It demonstrates comfort with linked list traversal, pointer manipulation, and state tracking through a carry variable. Mentioning the recursive version shows deeper understanding, but the iterative approach is usually preferred due to constant auxiliary space and simpler control flow.
This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.
This C implementation employs a dummy head node to start building the resultant list. A 'carry' variable is used to keep track of any overflow beyond a single digit, which is added to the next higher digit. The values are summed, and their result is split into carry and remainder, which becomes the node value. The iteration continues until both input lists are exhausted. The remaining carry is checked to append another node if needed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.
The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.
In this C solution, we define a helper function addTwoNumbersRecursive that takes the two input lists and a carry. The function recursively creates new nodes based on the summed values ensuring that carry is also considered. The base case returns NULL when ends of both lists and no carry remain.
C++
Java
Python
C#
JavaScript
Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once. |
| Recursive Approach | Time Complexity: O(max(m, n)) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Digit Addition | O(n) | O(1) | General case and most interview settings; memory efficient and easy to reason about |
| Recursive Addition | O(n) | O(n) | When demonstrating recursion patterns or functional style solutions |
Add Two Numbers - Leetcode 2 - Python • NeetCode • 293,331 views views
Watch 9 more video solutions →Practice Add Two Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor