Add 1 to a Linked List Number | GFG Practice | Optimal Solution

You are given a linked list that represents a number. Each node contains a single digit, and the digits are stored in the same order as they appear in the number. Add 1 to this number and return the head of the modified linked list.

Here’s the [Problem Link] to begin with.

Input: LinkedList: 4->5->6
Output: 457

Explanation: 4->5->6 represents 456 and when 1 is added it becomes 457. 

Input: LinkedList: 1->2->3
Output: 124
 
Explanation:  1->2->3 represents 123 and when 1 is added it becomes 124. 

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= len(list) <= 10⁵
0 <= list[i] <= 9

Solution: Optimal Approach (Reverse and Add)

Intuition

Think of this like adding 1 to a number written on paper! When we add 1 to a number, we start from the rightmost digit (least significant). If that digit is 9, it becomes 0 and we carry 1 to the next digit. We keep doing this until we don’t have a carry anymore. Since our linked list starts from the leftmost digit, we need to reverse it first, do our addition, and then reverse it back!

Detailed Approach

1. Reverse the List: Since we need to add from the least significant digit, reverse the entire linked list
2. Add One: Start from the new head (which was the last digit originally) and add 1
3. Handle Carry: If the current digit is 9, it becomes 0 and we carry 1 to the next digit
4. Continue with Carry: Keep propagating the carry until we find a digit that’s not 9
5. Handle New Digit: If we reach the end with a carry, create a new node with value 1
6. Reverse Back: Reverse the list again to restore the original order

Code

class Solution:
    def reverse(self, head):
        temp = head
        prev = None
        while temp is not None:
            front = temp.next      # Store next node before breaking link
            temp.next = prev       # Reverse the link
            prev = temp            # Move prev forward
            temp = front           # Move temp forward
        return prev               # Return new head of reversed list

    def addOne(self, head):
        # Step 1: Reverse the linked list to process from least significant digit
        new_head = self.reverse(head)
        temp = new_head
        carry = 0
        
        # Step 2: Add 1 and handle carry propagation
        while temp:
            if temp.data == 9:
                carry = 1         # Set carry for next digit
                temp.data = 0     # Current digit becomes 0
            else:
                temp.data = temp.data + 1  # Simply add 1 to current digit
                break             # No more carry needed, we're done
            
            # Step 3: Handle case where we need to add new digit at front
            if temp.next is None:
                if carry == 1:
                    temp.next = Node(1)  # Add new node with value 1
                    break
            temp = temp.next
        
        # Step 4: Reverse the list back to original order
        return self.reverse(new_head)

Code Explanation

This solution works in three main phases. First, we reverse the entire linked list so we can process digits from right to left (least to most significant). Then we add 1 starting from the new head. If the current digit is 9, it becomes 0 and we set a carry for the next digit. If it’s not 9, we simply add 1 and we’re done. The tricky part is handling the case where we have a carry even after processing all digits (like 999 → 1000) – in this case, we create a new node. Finally, we reverse the list back to its original order.

Dry Run

Let’s trace through: 9 -> 9 -> 9 (represents 999)

Step 1: Reverse the list

• Original: 9 -> 9 -> 9
• Reversed: 9 -> 9 -> 9 (same in this case)

Step 2: Add 1 and handle carry

• Start at first 9: data = 9, set carry = 1, data becomes 0
• Move to second 9: data = 9, set carry = 1, data becomes 0
• Move to third 9: data = 9, set carry = 1, data becomes 0
• Reached end with carry = 1, create new node: 0 -> 0 -> 0 -> 1

Step 3: Reverse back

• Current: 0 -> 0 -> 0 -> 1
• Reversed: 1 -> 0 -> 0 -> 0

Result: 1 -> 0 -> 0 -> 0 (represents 1000)

Let’s also trace: 1 -> 2 -> 3 (represents 123)

Step 1: Reverse the list

• Original: 1 -> 2 -> 3
• Reversed: 3 -> 2 -> 1

Step 2: Add 1

• Start at 3: data = 3 (not 9), so data becomes 4, break

Step 3: Reverse back

• Current: 4 -> 2 -> 1
• Reversed: 1 -> 2 -> 4

Result: 1 -> 2 -> 4 (represents 124)

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list three times (two reversals + one addition), but it’s still linear
• Space Complexity: O(1) – We only use a few pointer variables, no extra space needed

Simplifying It

This approach is like doing manual addition on paper, but since the number is written left-to-right and we need to add from right-to-left, we first flip the paper, do our addition, and then flip it back. The key insight is that we need to access the least significant digit first, which requires reversing the list.

Alternative Approach (Without Reversing)

While the reverse approach is optimal, there’s also a recursive solution that doesn’t require reversing:

Concept: Use recursion to reach the end of the list first, then add 1 and propagate the carry back up through the recursive calls.

Intuition: It’s like having a chain of people passing a message. The last person adds 1 and passes any carry back to the previous person.

However, this approach has O(n) space complexity due to the recursion stack, making the reverse approach more space-efficient.

Summary

The reverse and add approach is generally preferred because it uses constant space while maintaining linear time complexity. The key insight is that addition naturally works from right to left, so we reverse the list to make the rightmost digit accessible first.

This problem beautifully demonstrates how understanding the fundamental nature of an operation (addition works right to left) can lead to an elegant solution by adapting the data structure (reversing the list) to match the operation’s requirements!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.