Add 1 to Linked List
Problem link: https://www.geeksforgeeks.org/problems/add-1-to-a-number-represented-as-linked-list/1
Problem Statement
You are given a linked list representing a non-negative number. Each node contains a single digit. The digits are stored such that the most significant digit is at the head.
Add 1 to the number and return the head of the modified linked list.
Input
- Head of linked list representing a number
- Example: 1 → 9 → 9 represents 199
Output
- Return head of updated linked list after adding 1
Example
Input: 1 → 9 → 9
Output: 2 → 0 → 0
Explanation
199 + 1 = 200
Carry propagates from last node to first.
Brute Force
Intuition
Convert the linked list into a number, add 1, then rebuild the linked list. This works but is not efficient for large numbers.
Approach
- Traverse list and convert to integer
- Add 1
- Convert number back to linked list
Dry Run
Convert 1→9→9 → 199 199 + 1 = 200 Rebuild → 2→0→0
Visualization
Original number represented as linked list
Code (Java)
// Not recommended due to overflow risk
// Skipping implementation
Complexity Analysis
Conversion requires O(N), but integer overflow makes it impractical.
Optimal Solution
Intuition
We need to simulate addition from the least significant digit. Since linked list is in forward order, reverse it, add 1, handle carry, and reverse back.
Approach
- Reverse the linked list
- Add 1 to head
- Propagate carry
- Reverse list again
- If carry remains, add new node at front
Dry Run
Original: 1→9→9 Reverse: 9→9→1
Add 1: 9+1=10 → 0 carry 1 9+1=10 → 0 carry 1 1+1=2 → carry 0
Reverse back → 2→0→0
Visualization
1 → 9 → 9 represents 199
Code (Java)
class Solution {
static class Node {
int data;
Node next;
Node(int d) { data = d; }
}
public Node addOne(Node head) {
head = reverse(head);
Node curr = head;
int carry = 1;
while (curr != null && carry > 0) {
int sum = curr.data + carry;
curr.data = sum % 10;
carry = sum / 10;
if (curr.next == null && carry > 0) {
curr.next = new Node(carry);
carry = 0;
break;
}
curr = curr.next;
}
return reverse(head);
}
private Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
Complexity Analysis
We traverse list twice (reverse + process) → O(N), constant space.
Quick Revision (Brute Force)
- Convert to number
- Add 1
- Rebuild list
- Overflow risk
Quick Revision (Optimal)
- Reverse list
- Add with carry
- Reverse back
- Handle final carry