Add 1 to a Number Represented as Linked List

Problem Statement

A number is represented as a linked list where each node contains a single digit. The digits are stored in order (most significant digit first). Add 1 to this number and return the resulting linked list.

Example

Brute Force Approach (Reverse, Add, Reverse)

Intuition

Since addition starts from the least significant digit (rightmost), we can:

1. Reverse the linked list
2. Add 1 to the first node and handle carry
3. Reverse the list back

Algorithm

1. Reverse the linked list
2. Add 1 to the first node
3. Propagate carry through the list
4. If carry remains, add a new node
5. Reverse the list back

Implementation

Complexity Analysis

• Time Complexity: O(n) - Three passes (reverse, add, reverse)
• Space Complexity: O(1) - Only using constant extra space (iterative reversal)

Optimal Approach (Recursion)

Intuition

We can use recursion to traverse to the end of the list first, then handle the addition and carry while backtracking. This simulates adding from the least significant digit.

Algorithm

1. Recursively go to the end of the list
2. While backtracking, add the carry to each node
3. Return the carry to the previous call
4. If carry remains at the head, create a new node

Visualization

Implementation

Complexity Analysis

• Time Complexity: O(n) - Visit each node once
• Space Complexity: O(n) - Recursive call stack

Alternative Optimal Approach (Find Rightmost Non-9)

Intuition

Instead of reversing or using recursion, we can observe that:

• If a digit is not 9, adding 1 just increments it
• If digits are 9, they become 0 and we carry over

Find the rightmost non-9 digit, increment it, and set all digits to its right to 0.

Algorithm

1. Find the rightmost node that is not 9
2. If no such node exists (all 9s), create a new head with value 1
3. Otherwise, increment that node
4. Set all nodes to its right to 0

Implementation

Complexity Analysis

• Time Complexity: O(n) - Two passes maximum
• Space Complexity: O(1) - Only using constant extra space

Comparison of Approaches

| Approach | Time | Space | Pros | Cons | |----------|------|-------|------|------| | Reverse + Add + Reverse | O(n) | O(1) | Iterative, constant space | Three passes | | Recursion | O(n) | O(n) | Clean, intuitive | Stack space | | Find Rightmost Non-9 | O(n) | O(1) | Most elegant, efficient | Requires insight |

Key Takeaways

1. The rightmost non-9 approach is the most elegant O(n) time, O(1) space solution
2. Recursion naturally handles the "add from right" requirement but uses O(n) space
3. The reverse approach is straightforward but requires three passes
4. Edge case: all 9s require creating a new head node
5. This problem teaches important concepts about carry propagation
6. Similar logic applies to adding two numbers represented as linked lists