Watch 10 video solutions for Add Two Numbers, a medium level problem involving Linked List, Math, Recursion. This walkthrough by NeetCode has 293,331 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |