Problem Description

You are given a non-negative integer that is represented as a singly linked list, where each node contains a single digit. The digits are arranged such that the most significant digit comes first (at the head of the list).

Your task is to add one to this integer and return the result as a linked list in the same format.

For example:

• If the linked list represents 1 -> 2 -> 3 (which represents the number 123), after adding one, it should become 1 -> 2 -> 4 (representing 124).
• If the linked list represents 9 -> 9 -> 9 (which represents the number 999), after adding one, it should become 1 -> 0 -> 0 -> 0 (representing 1000).

The challenge involves handling the carry operation properly, especially when there are consecutive 9s at the end of the number, as they will all become 0 with a carry propagating forward.

Intuition

When we add 1 to a number, the key insight is that we only need to handle the carry operation for consecutive 9s at the end. Think about it: when you add 1 to 1299, you get 1300. The 9s at the end all become 0, and the last non-9 digit (which is 2) becomes 3.

This observation leads us to realize that we don't need to process the entire number digit by digit with carry propagation. Instead, we can find the rightmost digit that is not 9, increment it by 1, and then set all digits after it to 0.

For example:

• 1234 + 1 = 1235: The last non-9 is 4, we change it to 5
• 1299 + 1 = 1300: The last non-9 is 2, we change it to 3, and all 9s after it become 0
• 999 + 1 = 1000: All digits are 9, so we need an extra digit at the front

The tricky part is handling the edge case where all digits are 9 (like 999). In this case, we need to add an extra digit 1 at the beginning. To handle this elegantly, we can use a dummy node with value 0 at the start. If all original digits are 9, this dummy node will be incremented to 1 and become part of our answer. Otherwise, we can simply skip it when returning the result.

This approach is more efficient than simulating the actual addition with carry, as we only need to traverse the list once to find the critical position (the last non-9 digit) and then update the necessary nodes.

Solution Approach

The implementation uses a single traversal approach with a dummy node to handle edge cases elegantly.

Step 1: Set up a dummy node We create a dummy node with value 0 and point it to the original head. This dummy node serves two purposes:

• It acts as a potential new most significant digit if all original digits are 9
• It provides a starting point for our target pointer

dummy = ListNode(0, head)
target = dummy

Step 2: Find the rightmost non-9 digit We traverse the entire linked list while maintaining a pointer target that tracks the last node we encountered that isn't 9. This is the node we'll need to increment.

while head:
    if head.val != 9:
        target = head
    head = head.next

During this traversal:

• If we find a node with value not equal to 9, we update target to point to it
• We continue until we reach the end of the list
• After the loop, target points to the rightmost non-9 digit (or the dummy if all digits are 9)

Step 3: Increment and reset Once we've identified the target node, we increment it by 1 and then set all nodes after it to 0:

target.val += 1
target = target.next
while target:
    target.val = 0
    target = target.next

This handles the carry propagation - all 9s after the incremented digit become 0s.

Step 4: Return the result Finally, we check if the dummy node was used (its value would be 1 if all original digits were 9):

return dummy if dummy.val else dummy.next

• If dummy.val is 1, we return dummy (we needed the extra digit)
• Otherwise, we return dummy.next (the original head, now modified)

This approach runs in O(n) time with a single pass through the list and uses O(1) extra space.

Example Walkthrough

Let's walk through the solution with the input 1 -> 2 -> 9 -> 9 (representing 1299).

Step 1: Initialize with dummy node

dummy(0) -> 1 -> 2 -> 9 -> 9
target = dummy

We create a dummy node with value 0 pointing to the head, and initialize target to point to dummy.

Step 2: Traverse to find rightmost non-9

• Start at node 1:
  • 1 ≠ 9, so update target = node(1)
  • Move to next node
• At node 2:
  • 2 ≠ 9, so update target = node(2)
  • Move to next node
• At node 9:
  • 9 = 9, so don't update target
  • Move to next node
• At node 9:
  • 9 = 9, so don't update target
  • Move to next node (null)

After traversal, target points to node 2 (the rightmost non-9 digit).

Step 3: Increment target and set following nodes to 0

• Increment target: node 2 becomes 3
• Move target to next node (first 9)
• Set to 0: first 9 becomes 0
• Move target to next node (second 9)
• Set to 0: second 9 becomes 0
• Move target to next node (null)

The list is now: dummy(0) -> 1 -> 3 -> 0 -> 0

Step 4: Return result Since dummy.val = 0 (not 1), we return dummy.next, which gives us: 1 -> 3 -> 0 -> 0 (representing 1300)

Edge Case Example: All 9s For input 9 -> 9 -> 9:

• After Step 2: target remains pointing to dummy (no non-9 found)
• After Step 3: dummy becomes 1, all original nodes become 0
• List becomes: 1 -> 0 -> 0 -> 0
• Since dummy.val = 1, we return dummy itself

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

The algorithm traverses the linked list twice:

1. First traversal: The while loop iterates through all nodes once to find the rightmost non-9 digit, taking O(n) time.
2. Second traversal: In the worst case (when all digits after the target node are 9s), we traverse from the target node to the end of the list to set them to 0, which is at most O(n) time.

Since both traversals are sequential and not nested, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• dummy: A single additional node created at the beginning
• target: A pointer variable that references existing nodes
• head: A pointer variable used for traversal

No additional data structures that grow with input size are used. The algorithm modifies the linked list in-place, requiring only constant extra space regardless of the input size.

Common Pitfalls

Pitfall 1: Forgetting to Handle the All-9s Case

The Problem: A common mistake is trying to handle the carry operation without considering that all digits might be 9. Without proper handling, you might try to access a null pointer or fail to add the new most significant digit.

Why It Happens:

# Incorrect approach - doesn't handle all 9s properly
def plusOne_wrong(head):
    # Find rightmost non-9
    target = None
    current = head
    while current:
        if current.val != 9:
            target = current
        current = current.next
  
    # BUG: If all digits are 9, target is None!
    target.val += 1  # This will crash with AttributeError
    # ...

The Solution: Always use a dummy node that acts as a sentinel. This ensures you always have a valid node to increment:

dummy = ListNode(0, head)
rightmost_not_nine = dummy  # Guaranteed to have a valid node

Pitfall 2: Using Recursion or Stack (Space Inefficiency)

The Problem: Many developers instinctively reach for recursion or a stack to handle the carry from right to left, which uses O(n) extra space.

Why It Happens:

# Space-inefficient recursive approach
def plusOne_recursive(head):
    def helper(node):
        if not node:
            return 1
        carry = helper(node.next)
        total = node.val + carry
        node.val = total % 10
        return total // 10
  
    carry = helper(head)
    if carry:
        new_head = ListNode(1)
        new_head.next = head
        return new_head
    return head

The Solution: The single-pass approach with the dummy node achieves the same result in O(1) space by identifying the rightmost non-9 digit first, then propagating changes forward.

Pitfall 3: Multiple Traversals

The Problem: Some solutions traverse the list multiple times - once to find the length, once to find where to add, and once to handle carries.

Why It Happens:

# Inefficient multi-pass approach
def plusOne_multipass(head):
    # First pass: count length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
  
    # Second pass: find position to increment
    # ... more traversals ...

The Solution: The optimal approach combines all operations into a single traversal, tracking the rightmost non-9 digit as we go, making the algorithm more efficient with just one pass through the list.