Plus One Linked List

How it works

When adding one to a number, the only digits that change are trailing nines (which become zeros) and the rightmost non-nine digit (which increments by one). If all digits are nines, we need an extra digit at the front.

By using a sentinel node before the head, we handle the case where a new digit is needed (like 999 becoming 1000) without special logic. We simply find the rightmost non-nine digit, increment it, and set all following digits to zero.

Steps

1. Create a sentinel node with value 0 and point its next to the head.
2. Traverse the list to find the rightmost node that is not 9, storing a reference to it.
3. Increment that node's value by 1.
4. Set all nodes after it to 0 (these were all 9s that now carry over).
5. If the sentinel's value became 1 (meaning we needed an extra digit), return the sentinel. Otherwise, return its next node.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Where N is the length of the input list

Things to watch for

Forgetting the All-Nines Case

When all digits are 9 (e.g., 9 -> 9 -> 9), adding one requires a new node at the front. Without a sentinel node or explicit handling, you may return a result missing the leading 1, producing 0 -> 0 -> 0 instead of 1 -> 0 -> 0 -> 0.

Processing Left-to-Right Instead of Right-to-Left

Unlike arrays, singly linked lists cannot be traversed backwards. Naively incrementing from the head ignores how addition propagates carries from the least significant digit. This leads to incorrect results when carries need to cascade through multiple nodes.

Not Tracking the Rightmost Non-Nine Node

The key insight is that only trailing nines become zeros, and the rightmost non-nine digit increments. Failing to track this node forces you to either reverse the list or use recursion, both adding unnecessary complexity or space overhead.

class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        # sentinel head
        sentinel = ListNode(0)
        sentinel.next = head
        not_nine = sentinel

        # find the rightmost not-nine digit
        while head:
            if head.val != 9:
                not_nine = head
            head = head.next

        # increase this rightmost not-nine digit by 1
        not_nine.val += 1
        not_nine = not_nine.next

        # set all the following nines to zeros
        while not_nine:
            not_nine.val = 0
            not_nine = not_nine.next

        return sentinel if sentinel.val else sentinel.next

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        // sentinel head
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* notNine = sentinel;

        // find the rightmost not-nine digit
        while (head != nullptr) {
            if (head->val != 9) notNine = head;
            head = head->next;
        }
        // increase this rightmost not-nine digit by 1
        notNine->val++;
        notNine = notNine->next;
        // set all the following nines to zeros
        while (notNine != nullptr) {
            notNine->val = 0;
            notNine = notNine->next;
        }

        delete notNine;
        return sentinel->val != 0 ? sentinel : sentinel->next;
    }
};