Watch 10 video solutions for Add Two Numbers II, a medium level problem involving Linked List, Math, Stack. This walkthrough by codestorywithMIK has 14,522 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 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:
[1, 100].0 <= Node.val <= 9
Follow up: Could you solve it without reversing the input lists?
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 | 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 |