DSA problem
Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. Here the most-significant digit comes first, and each node contains a single digit. Add the two numbers and return the sum as a linked list, again with the most-significant digit first.
This is the natural variant of the classic "Add Two Numbers" problem, but the forward digit order is awkward: addition must proceed from the least-significant digit, which now sits at the tail of each list. A singly linked list cannot be walked backward, so you need a strategy to access the digits in reverse.
A common follow-up restriction is to solve it without modifying the input lists (so reversing them in place is discouraged). The cleanest non-destructive technique is to push every digit of each list onto its own stack. Popping the stacks then yields the digits from least-significant to most-significant, exactly the order addition needs.
The optimal approach loads both lists into two stacks, then repeatedly pops a digit from each (using 0 when a stack is empty), adds them with a carry, and builds the result. Because the result must be most-significant first, prepend each new node to the front of the output list so the digits naturally end up in the correct order. This runs in O(m + n) time and O(m + n) space.
Examples
l1 = [7,2,4,3], l2 = [5,6,4][7,8,0,7]l1 = [2,4,3], l2 = [5,6,4][8,0,7]l1 = [0], l2 = [0][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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.