Problem statement

A non-negative integer is stored in a singly linked list, one decimal digit per node, with the most significant digit at the head. The number has no leading zeros, except for the number 0 itself.

Add 1 to the number and return the head of the list representing the result, in the same form.

Example 1

Input: head = [4,5,6]
Output: [4,5,7]
Explanation: 456 + 1 = 457.

Example 2

Input: head = [1,2,9,9]
Output: [1,3,0,0]
Explanation: 1299 + 1 = 1300: the trailing 9s turn into 0s and the 2 becomes 3.

Example 3

Input: head = [9,9]
Output: [1,0,0]
Explanation: 99 + 1 = 100 — every digit is 9, so a new leading digit appears.

Constraints

• The number of nodes in the list is in the range [1, 10^5]
• 0 <= Node.val <= 9
• The number has no leading zeros, except the number 0 itself

Hints for Add 1 to a Number Represented as Linked List

1. Hint 1

   Adding 1 only changes the trailing run of 9s and the digit just before it.

2. Hint 2

   Find the last node whose digit is not 9 in one forward pass.

3. Hint 3

   Increment that node and set every node after it to 0. If there is no such node, every digit is 9: put a new node 1 in front and set all old digits to 0.

How to solve Add 1 to a Number Represented as Linked List

A carry only travels through 9s. So the digit that absorbs the +1 is the last digit that is not 9; everything after it was 9 and becomes 0.

Approach

1. Walk the list and remember the last node whose value is not 9.
2. If there is one, increase it by 1 and set every node after it to 0; return head.
3. Otherwise every digit is 9: set them all to 0 and return a new node 1 placed in front of head.

Why it works

Adding 1 to x 9 9 … 9 (where x != 9) gives (x + 1) 0 0 … 0 — the carry dies at x because x + 1 <= 9. Digits before x are untouched. When there is no such x the number is 10^k - 1 and the result is 10^k.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Converting the list to a built-in integer overflows for long lists.
• Reversing the list twice also works but costs two extra passes; recursion from the tail risks a stack overflow on 10^5 nodes.
• The number 0 becomes 1.

Reference solution

Python

from typing import Optional

def addOne(head: Optional[ListNode]) -> Optional[ListNode]:
    last = None
    cur = head
    while cur:
        if cur.val != 9:
            last = cur
        cur = cur.next
    if last is None:
        result, cur = ListNode(1, head), head
    else:
        last.val += 1
        result, cur = head, last.next
    while cur:
        cur.val = 0
        cur = cur.next
    return result

Java

public static ListNode addOne(ListNode head) {
    ListNode last = null, cur;
    for (cur = head; cur != null; cur = cur.next) if (cur.val != 9) last = cur;
    ListNode result = head;
    if (last == null) { result = new ListNode(1, head); cur = head; }
    else { last.val += 1; cur = last.next; }
    for (; cur != null; cur = cur.next) cur.val = 0;
    return result;
}

C++

ListNode* addOne(ListNode* head) {
    ListNode *last = nullptr, *cur;
    for (cur = head; cur; cur = cur->next) if (cur->val != 9) last = cur;
    ListNode* result = head;
    if (!last) { result = new ListNode(1, head); cur = head; }
    else { last->val += 1; cur = last->next; }
    for (; cur; cur = cur->next) cur->val = 0;
    return result;
}

JavaScript

var addOne = function(head) {
    var last = null, cur;
    for (cur = head; cur !== null; cur = cur.next) if (cur.val !== 9) last = cur;
    var result = head;
    if (last === null) { result = new ListNode(1, head); cur = head; }
    else { last.val += 1; cur = last.next; }
    for (; cur !== null; cur = cur.next) cur.val = 0;
    return result;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium
• Count Special Subsequences Medium