Plus One Linked List

medium linked list

Problem

Given a non-empty linked list representing a non-negative integer, add one to it (most significant digit first).

Input[1, 2, 3]

Output[1, 2, 4]

No carry needed — last node 3 → 4.

digits (comma-separated)

def plus_one(head):
    not_nine = sentinel = type(head)(0)
    sentinel.next = head
    cur = head
    while cur:
        if cur.val != 9: not_nine = cur
        cur = cur.next
    not_nine.val += 1
    n = not_nine.next
    while n:
        n.val = 0
        n = n.next
    return head if sentinel.next is head and sentinel.val == 0 else sentinel

function plusOne(head) {
  const sentinel = { val: 0, next: head };
  let notNine = sentinel, cur = head;
  while (cur) {
    if (cur.val !== 9) notNine = cur;
    cur = cur.next;
  }
  notNine.val += 1;
  let n = notNine.next;
  while (n) { n.val = 0; n = n.next; }
  return sentinel.val === 0 ? sentinel.next : sentinel;
}

class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode sentinel = new ListNode(0); sentinel.next = head;
        ListNode notNine = sentinel, cur = head;
        while (cur != null) {
            if (cur.val != 9) notNine = cur;
            cur = cur.next;
        }
        notNine.val++;
        ListNode n = notNine.next;
        while (n != null) { n.val = 0; n = n.next; }
        return sentinel.val == 0 ? sentinel.next : sentinel;
    }
}

ListNode* plusOne(ListNode* head) {
    ListNode sentinel(0); sentinel.next = head;
    ListNode* notNine = &sentinel; ListNode* cur = head;
    while (cur) { if (cur->val != 9) notNine = cur; cur = cur->next; }
    notNine->val++;
    for (ListNode* n = notNine->next; n; n = n->next) n->val = 0;
    return sentinel.val == 0 ? sentinel.next : new ListNode(1, sentinel.next);
}

Explanation

Adding one to a number is easy unless the last digits are 9s, because a 9 becomes 0 and carries over. The clever idea here is to find the rightmost digit that is not a 9 — that is the only digit that actually needs to increase.

We add a sentinel node in front (value 0) so there is always a non-9 digit even if the whole number is all 9s. We scan the list and remember the last node whose value is not 9 in not_nine. After the scan, we increment that node and set every digit after it to 0.

This works because all the trailing 9s turn into 0s when the carry passes through them, and the first non-9 to their left simply goes up by one and absorbs the carry. The sentinel handles the case like 999 → 1000 where a new leading digit is needed.

Example: [1, 2, 3]. The last non-9 is the 3, so it becomes 4 and there are no digits after it to zero out, giving [1, 2, 4]. For [1, 9, 9] the 1 becomes 2 and the 9s become 0, giving [2, 0, 0].

At the end we return the sentinel only if it was actually used as a new leading 1, otherwise we return the original head.

Time: O(n) Space: O(1)