Add Two Numbers Stored in Forward Order
Solve this Probleml1 and l2, each representing a non-negative integer with its digits stored in the usual order — the head node holds the most significant digit. Add the two numbers and return the sum as a linked list in that same forward order.
Unlike the reverse-order version of this problem, the head here is the most significant digit — the one that might need to change if a carry ripples all the way through, which a singly linked list can't easily do while reading forward. A stackStack for Order ReversalPushing every element of a sequence onto a stack and then popping them back off visits them in reverse order — without ever touching or reversing the original structure. It's a common alternative to in-place reversal when the original data needs to stay untouched. flips the visiting order to least-significant-first — matching how addition naturally carries — without disturbing either input list.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in l1, l2 ≤ 100 - ◆
0 ≤ node value ≤ 9 - ◆
Each list represents a non-negative integer with digits stored in the usual left-to-right order — the head is the most significant digit — and has no leading zeros, except the number 0 itself
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node addTwoNumbers(Node l1, Node l2) { |
| 3 | Deque<Integer> stack1 = new ArrayDeque<>(); |
| 4 | while (l1 != null) { |
| 5 | stack1.push(l1.val); |
| 6 | l1 = l1.next; |
| 7 | } |
| 8 | Deque<Integer> stack2 = new ArrayDeque<>(); |
| 9 | while (l2 != null) { |
| 10 | stack2.push(l2.val); |
| 11 | l2 = l2.next; |
| 12 | } |
| 13 | Node result = null; |
| 14 | int carry = 0; |
| 15 | while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) { |
| 16 | int x = stack1.isEmpty() ? 0 : stack1.pop(); |
| 17 | int y = stack2.isEmpty() ? 0 : stack2.pop(); |
| 18 | int sum = x + y + carry; |
| 19 | carry = sum / 10; |
| 20 | result = new Node(sum % 10, result); |
| 21 | } |
| 22 | return result; |
| 23 | } |
| 24 | } |
| 25 |
[]stack1 starts empty — every value of l1 will be pushed onto it.
Approach & Solutions
Brute Force — Rebuild Both Numbers, Add, Convert the Sum Back
GoodSince each list already stores its digits most-significant-first — the same order people read numbers in — walk each list once, building up num = num * 10 + digit to reconstruct the actual value. Add the two numbers normally, convert the sum to a string, and build the result list directly from those characters — no reversal needed anywhere, since both the input order and the string's digit order already match what the answer needs.
O(n + m)O(n + m)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node addTwoNumbers(Node l1, Node l2) {
9 long num1 = 0;
10 Node curr = l1;
11 while (curr != null) {
12 num1 = num1 * 10 + curr.val;
13 curr = curr.next;
14 }
15 long num2 = 0;
16 curr = l2;
17 while (curr != null) {
18 num2 = num2 * 10 + curr.val;
19 curr = curr.next;
20 }
21 long sum = num1 + num2;
22 String digits = Long.toString(sum);
23 Node dummy = new Node(0);
24 Node tail = dummy;
25 for (int i = 0; i < digits.length(); i++) {
26 tail.next = new Node(digits.charAt(i) - '0');
27 tail = tail.next;
28 }
29 return dummy.next;
30 }
31}Optimal — Two Stacks, Pop and Add With Carry, Prepend New Nodes
OptimalPush every value of l1 onto one stack and every value of l2 onto another — popping now naturally visits each list least-significant digit first, without ever reversing (or otherwise mutating) the original lists. Pop from both stacks together, add with a carry, and prepend (not append) each new digit to the result — since digits are produced least-significant first but the answer needs most-significant first, prepending puts each one exactly where it belongs.
O(n + m)O(n + m)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node addTwoNumbers(Node l1, Node l2) {
9 Deque<Integer> stack1 = new ArrayDeque<>();
10 while (l1 != null) {
11 stack1.push(l1.val);
12 l1 = l1.next;
13 }
14 Deque<Integer> stack2 = new ArrayDeque<>();
15 while (l2 != null) {
16 stack2.push(l2.val);
17 l2 = l2.next;
18 }
19 Node result = null;
20 int carry = 0;
21 while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
22 int x = stack1.isEmpty() ? 0 : stack1.pop();
23 int y = stack2.isEmpty() ? 0 : stack2.pop();
24 int sum = x + y + carry;
25 carry = sum / 10;
26 result = new Node(sum % 10, result);
27 }
28 return result;
29 }
30}