Intuition
Addition must start at the least-significant digit, but the most-significant digit comes first here. Push both lists onto stacks so popping yields digits from the low end; add with a carry, and prepend each new digit to the front of the result.
Explanation
The digits are in the wrong order for addition
Pencil-and-paper addition goes right-to-left (units first), but these lists give the most-significant digit first. Two stacks fix the ordering: push every digit of each list, then pop — popping returns digits from least- to most-significant.
Add with a carry, build the result front-to-back
s1 = stack of l1's digits; s2 = stack of l2's digits
carry = 0; head = None
while s1 or s2 or carry:
v = carry + (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)
carry = v // 10
node = new Node(v % 10)
node.next = head # prepend so the result stays most-significant-first
head = node
return head
Prepending each freshly computed digit automatically produces the answer in most-significant-first order.
Worked example
l1 = 7->2->4->3 (7243), l2 = 5->6->4 (564).
Pop pairs from the low end: 3+4=7; 4+6=10 → digit 0 carry 1; 2+5+1=8; 7+0=7. Prepending gives 7->8->0->7 = 7807 (7243 + 564).
Complexity
- Time: O(n + m).
- Space: O(n + m) for the stacks.
Implementation
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> s1 = new ArrayDeque<>();
Deque<Integer> s2 = new ArrayDeque<>();
while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
while (l2 != null) { s2.push(l2.val); l2 = l2.next; }
int carry = 0;
ListNode head = null;
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
int v = carry + (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
carry = v / 10;
ListNode node = new ListNode(v % 10);
node.next = head;
head = node;
}
return head;
}
}