LeetCode 369 Plus One Linked List Solution & Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Linked List Traversal - Iterating through nodes using next pointers to find specific elements
Sentinel/Dummy Node Pattern - Using a placeholder node before the head to simplify edge cases like inserting at the beginning
Carry Propagation - Understanding how addition works digit by digit, where trailing 9s become 0s and carry forward

1. Sentinel Head + Textbook Addition

Intuition

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.

Algorithm

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

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 != null) {
            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 != null) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val != 0 ? sentinel : 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;
    }
};

class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    plusOne(head) {
        // sentinel head
        const sentinel = new ListNode(0);
        sentinel.next = head;
        let notNine = sentinel;

        // find the rightmost not-nine digit
        while (head) {
            if (head.val !== 9) {
                notNine = head;
            }
            head = head.next;
        }

        // increase this rightmost not-nine digit by 1
        notNine.val += 1;
        notNine = notNine.next;

        // set all the following nines to zeros
        while (notNine) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val !== 0 ? sentinel : sentinel.next;
    }
}

public 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 != null) {
            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 != null) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val != 0 ? sentinel : sentinel.next;
    }
}

func plusOne(head *ListNode) *ListNode {
    // sentinel head
    sentinel := &ListNode{Val: 0, Next: head}
    notNine := sentinel

    // find the rightmost not-nine digit
    for head != nil {
        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
    for notNine != nil {
        notNine.Val = 0
        notNine = notNine.Next
    }

    if sentinel.Val != 0 {
        return sentinel
    }
    return sentinel.Next
}

class Solution {
    fun plusOne(head: ListNode?): ListNode? {
        // sentinel head
        val sentinel = ListNode(0)
        sentinel.next = head
        var notNine: ListNode? = sentinel
        var curr = head

        // find the rightmost not-nine digit
        while (curr != null) {
            if (curr.`val` != 9) {
                notNine = curr
            }
            curr = curr.next
        }

        // increase this rightmost not-nine digit by 1
        notNine!!.`val`++
        notNine = notNine.next

        // set all the following nines to zeros
        while (notNine != null) {
            notNine.`val` = 0
            notNine = notNine.next
        }

        return if (sentinel.`val` != 0) sentinel else sentinel.next
    }
}

class Solution {
    func plusOne(_ head: ListNode?) -> ListNode? {
        // sentinel head
        let sentinel = ListNode(0)
        sentinel.next = head
        var notNine: ListNode? = sentinel
        var curr = head

        // find the rightmost not-nine digit
        while curr != nil {
            if curr!.val != 9 {
                notNine = curr
            }
            curr = curr?.next
        }

        // increase this rightmost not-nine digit by 1
        notNine!.val += 1
        notNine = notNine?.next

        // set all the following nines to zeros
        while notNine != nil {
            notNine!.val = 0
            notNine = notNine?.next
        }

        return sentinel.val != 0 ? sentinel : sentinel.next
    }
}

impl Solution {
    pub fn plus_one(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // collect values into a vec for easier manipulation
        let mut vals = Vec::new();
        let mut cur = &head;
        while let Some(node) = cur {
            vals.push(node.val);
            cur = &node.next;
        }

        // find the rightmost not-nine digit
        let mut not_nine: i32 = -1; // sentinel position
        for (i, &v) in vals.iter().enumerate() {
            if v != 9 {
                not_nine = i as i32;
            }
        }

        // increase the rightmost not-nine digit by 1 and set following to 0
        if not_nine == -1 {
            // all digits are 9, need extra leading 1
            let mut result = vec![1];
            result.resize(vals.len() + 1, 0);
            // build linked list from result
            let mut head = None;
            for &v in result.iter().rev() {
                let mut node = ListNode::new(v);
                node.next = head;
                head = Some(Box::new(node));
            }
            return head;
        }

        vals[not_nine as usize] += 1;
        for i in (not_nine as usize + 1)..vals.len() {
            vals[i] = 0;
        }

        // build linked list from vals
        let mut head = None;
        for &v in vals.iter().rev() {
            let mut node = ListNode::new(v);
            node.next = head;
            head = Some(Box::new(node));
        }
        head
    }
}

Time & Space Complexity

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

Where $N$ is the length of the input list

Common Pitfalls

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.