Increment a Number Stored as a Linked List
Solve this Problem
Given the
head of a singly linked list where each node holds one digit of a non-negative number — most significant digit first — add 1 to the number and return the head of the resulting list.
This looks like ordinary addition, but a linked list can only walk forward, while carrying a +1 naturally flows from the last digit toward the first. The optimal solution resolves that mismatch with a reversal trickReverse, Operate, Reverse BackA common pattern for list problems where the natural order of operation runs opposite to the list's natural direction of traversal: reverse the list so the operation becomes a simple forward pass, do the work, then reverse back to restore the original order — all in O(1) extra space. — reverse the list so the least significant digit comes first, add with a simple forward-carrying pass, then reverse back.
Test Case 1:
Input:head = [1, 2, 9]
Output:[1, 3, 0]
Explanation:129 + 1 = 130.
Test Case 2:
Input:head = [9, 9, 9]
Output:[1, 0, 0, 0]
Explanation:999 + 1 = 1000 — the carry overflows into a brand-new leading digit.
Test Case 3:
Input:head = [0]
Output:[1]
Explanation:A single 0 becomes 1.
Constraints
- ◆
1 ≤ number of nodes in head ≤ 100 - ◆
0 ≤ node value ≤ 9 - ◆
The digits form a number with no leading zeros, except when the number itself is 0
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public Node addOne(Node head) { |
| 3 | Node prev = null, curr = head; |
| 4 | while (curr != null) { |
| 5 | Node next = curr.next; |
| 6 | curr.next = prev; |
| 7 | prev = curr; |
| 8 | curr = next; |
| 9 | } |
| 10 | head = prev; |
| 11 | |
| 12 | Node node = head, last = null; |
| 13 | int carry = 1; |
| 14 | while (node != null && carry > 0) { |
| 15 | int sum = node.val + carry; |
| 16 | node.val = sum % 10; |
| 17 | carry = sum / 10; |
| 18 | last = node; |
| 19 | node = node.next; |
| 20 | } |
| 21 | if (carry > 0) { |
| 22 | last.next = new Node(carry); |
| 23 | } |
| 24 | |
| 25 | prev = null; curr = head; |
| 26 | while (curr != null) { |
| 27 | Node next = curr.next; |
| 28 | curr.next = prev; |
| 29 | prev = curr; |
| 30 | curr = next; |
| 31 | } |
| 32 | return prev; |
| 33 | } |
| 34 | } |
| 35 |
Linked List
null
Linked Listnull
1
curr
2
9
Variables
prev
nullcurr
1INITIALIZE
prev starts null (nothing flipped yet, left panel) and curr starts at head (right panel, the untouched list).
Step 1 / 30
Approach & Solutions
Brute Force — Copy Digits to an Array, Add 1, Overwrite the List
GoodWalk the list once, copying every digit into an array. Do the elementary-school "add 1" carry arithmetic on the array from its last index backward — no need to touch the list yet. Then walk the list a second time, overwriting each node's value from the array. If a carry survives past the array's first index, prepend one new node for the overflow digit.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node addOne(Node head) {
9 List<Integer> digits = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 digits.add(curr.val);
13 curr = curr.next;
14 }
15 int i = digits.size() - 1;
16 int carry = 1;
17 while (i >= 0 && carry > 0) {
18 int sum = digits.get(i) + carry;
19 digits.set(i, sum % 10);
20 carry = sum / 10;
21 i--;
22 }
23 curr = head;
24 int idx = 0;
25 while (curr != null) {
26 curr.val = digits.get(idx);
27 curr = curr.next;
28 idx++;
29 }
30 if (carry > 0) {
31 return new Node(carry, head);
32 }
33 return head;
34 }
35}Optimal — Reverse, Add 1 With Carry In Place, Reverse Back
OptimalReverse the list so the least significant digit comes first — now a carry only ever needs to look at the very next node, exactly like adding by hand. Walk forward adding the carry in place (no extra array), and if a carry survives past the last node, attach one new node for it. Reverse the list back to restore the original digit order.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node addOne(Node head) {
9 Node prev = null, curr = head;
10 while (curr != null) {
11 Node next = curr.next;
12 curr.next = prev;
13 prev = curr;
14 curr = next;
15 }
16 head = prev;
17
18 Node node = head, last = null;
19 int carry = 1;
20 while (node != null && carry > 0) {
21 int sum = node.val + carry;
22 node.val = sum % 10;
23 carry = sum / 10;
24 last = node;
25 node = node.next;
26 }
27 if (carry > 0) {
28 last.next = new Node(carry);
29 }
30
31 prev = null; curr = head;
32 while (curr != null) {
33 Node next = curr.next;
34 curr.next = prev;
35 prev = curr;
36 curr = next;
37 }
38 return prev;
39 }
40}