Add Two Numbers II - Solution & Explanation
Problem Statement
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0] Output: [0]
Constraints:
- 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.
Follow up: Could you solve it without reversing the input lists?
Approach Overview
Problem Overview: Two non-empty linked lists represent two non‑negative integers. Each node stores a single digit and the most significant digit appears first. Add the numbers and return the result as a linked list in the same forward order.
The challenge comes from the forward ordering. Addition normally starts from the least significant digit, but a singly linked list gives access from the head only. You must either reverse the traversal order or simulate it with another structure.
Approach 1: Reversal of Linked Lists (Time: O(n), Space: O(1))
Reverse both input lists so the least significant digits appear first. After reversal, the problem becomes identical to the classic Add Two Numbers problem. Traverse both reversed lists, compute sum = digit1 + digit2 + carry, create nodes for sum % 10, and propagate the carry. Finally reverse the resulting list again to restore forward order.
This approach modifies the original lists but avoids extra auxiliary structures. The key operations are pointer reversal and standard digit-by-digit addition. It works well when in-place modification is allowed and you want constant auxiliary space. The algorithm mainly relies on pointer manipulation typical in linked list problems.
Approach 2: Stack Data Structure (Time: O(n), Space: O(n))
Push all digits from each linked list into two stacks. This reverses the processing order because stacks pop the most recently inserted element first. After both stacks are filled, repeatedly pop digits, compute the current sum with carry, and create nodes at the front of the result list.
The trick is inserting new nodes at the head of the result list so the final order remains forward. Each iteration performs constant work: two stack pops, a carry calculation, and a node insertion. This method preserves the original lists and cleanly simulates reverse traversal. The technique combines stack behavior with digit addition logic from math problems.
Recommended for interviews: The stack approach is typically expected because the problem explicitly avoids modifying input lists. It demonstrates understanding of order reversal using auxiliary data structures. The reversal approach is still valuable to discuss—it shows you recognize the reduction to the classic addition problem and understand linked list manipulation.
Approach 1: Using Reversal of Linked Lists
This approach involves reversing both linked lists to align the least significant digits and performing the addition operation similarly to how you would add numbers on paper. After the sum is calculated, the result is reversed to restore the original order.
This solution first reverses both input lists to facilitate adding from the least significant to the most significant digit. We traverse both lists, compute the sum for corresponding nodes, and keep track of any carry forward. The resulting linked list is constructed by prepending nodes. Finally, the resultant list is reversed to represent the correct number.
Complexity
Time Complexity: O(n + m) where n and m are the lengths of the two linked lists. We reverse both lists and then traverse them. Space Complexity: O(1) if we exclude the space required for the output list.
Approach 2: Using Stack Data Structure
Another efficient way to solve this problem is using stacks to store digits of both the numbers. This helps to access the least significant digits last, similar to reversing. This allows easier management of carry as we traverse backward effectively without modifying input lists explicitly.
In C, we use two stacks to hold digits of the linked lists. As we pop elements from the stacks, we calculate the sum, manage the carry, and construct the resultant list by prepending nodes.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of linked lists. Space Complexity: O(n + m), for storing numbers in stacks.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Reversal of Linked Lists | Time Complexity: O(n + m) where n and m are the lengths of the two linked lists. We reverse both lists and then traverse them. Space Complexity: O(1) if we exclude the space required for the output list. |
| Using Stack Data Structure | Time Complexity: O(n + m), where n and m are the lengths of linked lists. Space Complexity: O(n + m), for storing numbers in stacks. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reversal of Linked Lists | O(n) | O(1) | When modifying the input lists is acceptable and you want constant auxiliary space |
| Stack Data Structure | O(n) | O(n) | Preferred when input lists must remain unchanged and reverse traversal is required |
Video Solution
Add Two Numbers II | Follow Up Qn Also | 2 Approaches | AMAZON | MICROSOFT | Leetcode-445 • codestorywithMIK • 16,842 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Add Two Numbers II easy or hard?
Add Two Numbers II Python/Java solution
How to solve Add Two Numbers II in O(n)?
What is the best approach for Add Two Numbers II?
Is Add Two Numbers II asked at Google/Amazon/Meta?
What data structure is used in Add Two Numbers II?
What is the time complexity of Add Two Numbers II?
Ready to solve this problem?
Practice Add Two Numbers II with our built-in code editor and test cases.
Practice on FleetCode