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 two non‑negative integers. Each node stores a single digit, and digits are stored in reverse order. You add the two numbers and return the sum as a new linked list while correctly handling digit carry.
Approach 1: Iterative Linked List Addition (O(n) time, O(1) extra space)
Traverse both lists simultaneously while maintaining a carry value. At each step, read the current digit from each list (use 0 if a list is exhausted), compute sum = x + y + carry, store sum % 10 as the new node, and update carry = sum // 10. Move both pointers forward and append the new node to the result list. This works because digits are already stored in reverse order, so addition proceeds exactly like manual column addition from least significant digit to most.
The loop continues while either list still has nodes or a carry remains. A dummy head node simplifies result construction and avoids special handling for the first node. Time complexity is O(max(m,n)) because each node is processed once, and extra space is O(1) excluding the output list. This approach relies heavily on pointer manipulation in a linked list and basic math operations for carry propagation.
Approach 2: Recursive Digit Addition (O(n) time, O(n) space)
The same addition logic can be expressed recursively. Each recursive call processes one pair of nodes and returns the resulting node for that digit. Compute the digit sum and carry exactly as in the iterative method, create a node with sum % 10, and recursively compute the next node using the remaining list nodes and updated carry.
The recursion stops when both lists are exhausted and no carry remains. If a carry still exists after the final digits, create one last node to store it. Time complexity remains O(max(m,n)) since each digit is processed once. Space complexity becomes O(n) due to the call stack used by recursion. This version is concise and elegant but less memory‑efficient than the iterative solution.
Recommended for interviews: The iterative approach is what most interviewers expect. It demonstrates comfort with linked list traversal, pointer manipulation, and carry management. Explaining the recursive version afterward shows deeper understanding of the same logic expressed through recursion. Implementing the iterative solution correctly without edge‑case bugs (different list lengths, leftover carry) is usually the key evaluation point.
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.
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.
Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.
We traverse two linked lists l_1 and l_2 at the same time, and use the variable carry to indicate whether there is a carry.
Each time we traverse, we take out the current bit of the corresponding linked list, calculate the sum with the carry carry, and then update the value of the carry. Then we add the current bit to the answer linked list. If both linked lists are traversed, and the carry is 0, the traversal ends.
Finally, we return the head node of the answer linked list.
The time complexity is O(max (m, n)), where m and n are the lengths of the two linked lists. We need to traverse the entire position of the two linked lists, and each position only needs O(1) time. Ignoring the space consumption of the answer, the space complexity is O(1).
| 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)) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Linked List Addition | O(max(m,n)) | O(1) extra | Standard interview solution; best when you want minimal memory overhead |
| Recursive Digit Addition | O(max(m,n)) | O(n) | Useful when recursion is preferred for cleaner code or conceptual clarity |
Add Two Numbers - Leetcode 2 - Python • NeetCode • 356,565 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