NUHMAN.com

📘 Problem Statement

You are given a non-empty linked list representing a non-negative integer. The digits are stored in reverse order, and each node contains a single digit. Add one to the integer represented by the linked list and return the resulting linked list.

You must solve the problem without using any built-in libraries (such as a large integer library) and the solution should work within constant space complexity.

🧠 Key Insight

This problem is equivalent to adding one to a number stored in reverse order in a linked list. The key insight is that you need to:

1. Traverse the linked list, adding one to the last digit.
2. Handle the carry if the sum exceeds 9.
3. If the carry overflows after the last node, you need to add a new node.

We can solve this problem in one pass by iterating from the head of the linked list and simulating the addition of 1. To make the process easier, we can reverse the linked list first, perform the addition, and then reverse it back.

💡 Approach

1. Reverse the Linked List: Start by reversing the input linked list to make the addition process easier (start from the least significant digit).
2. Add One: Traverse the reversed list, adding one to the first node. If there's a carry, propagate it to the next node.
3. Handle Carry Over: If there's still a carry after processing all nodes, add a new node with the carry value.
4. Reverse the Linked List Again: Once the addition is complete, reverse the linked list back to its original order.

🐍 Python Code

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        # Helper function to reverse the linked list
        def reverse(node):
            prev = None
            while node:
                next_node = node.next
                node.next = prev
                prev = node
                node = next_node
            return prev
        
        # Reverse the list to start addition from the least significant digit
        head = reverse(head)
        
        current = head
        carry = 1  # Start with carry 1 to add the '1' to the number
        while current:
            sum_val = current.val + carry
            current.val = sum_val % 10
            carry = sum_val // 10
            if carry == 0:
                break
            current = current.next
        
        # If there is a carry left, create a new node
        if carry:
            current.next = ListNode(carry)
        
        # Reverse the list again to restore the original order
        return reverse(head)

🔍 Step-by-Step Explanation

1. Reverse the Linked List

python

head = reverse(head)

• Reversing the linked list simplifies the addition process, as we start from the least significant digit, making the carry propagation straightforward.

2. Add One to the Number

python

current = head
carry = 1
while current:
    sum_val = current.val + carry
    current.val = sum_val % 10
    carry = sum_val // 10
    if carry == 0:
        break
    current = current.next

• Start from the head of the reversed list, add 1 (the carry) to the current node's value, and update the node's value to sum_val % 10 (to get the digit).
• Propagate the carry to the next node if the sum exceeds 9 (i.e., carry = sum_val // 10).
• If there's no carry left, break the loop early.

3. Handle Carry Over

python

if carry:
    current.next = ListNode(carry)

• If there's still a carry left after processing all nodes (i.e., the original number was all 9s), create a new node with the carry value.

4. Reverse the Linked List Again

python

return reverse(head)

• Finally, reverse the list again to restore it to its original order, since we worked on the reversed list during the addition.

💡 Example

python

Input: head = [9,9,9]
Output: [0,0,0,1]
Explanation: The number represented by the linked list is 999. Adding 1 gives 1000, which is represented as the linked list [0, 0, 0, 1].

Input: head = [1,2,3]
Output: [1,2,4]
Explanation: The number represented by the linked list is 321. Adding 1 gives 322, which is represented as the linked list [2, 2, 3].

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: The algorithm runs in O(n) time because we reverse the linked list twice and perform a constant amount of work for each node.
• Space Complexity: The space complexity is O(1) because we are only using a few variables (no extra space for additional data structures).

🧵 Final Thoughts

The Plus One Linked List problem is a great exercise in linked list manipulation. The key insights here are:

• Reversing the linked list makes the carry propagation process easier.
• Handling carries properly ensures that the result is accurate even when all digits are 9 (e.g., [9, 9, 9] -> [0, 0, 0, 1]).
• Reversing the list at the end restores the original order.

This approach has optimal time and space complexity and can be easily adapted to other problems that require linked list manipulation.