Add 1 to a Linked List Number

Intuitionthe carry starts at the end, but the list starts at the front

Adding one affects the least significant digit first. If that digit is below 9, you increase it and stop. If it is 9, it becomes 0 and the carry continues to the digit before it. This is exactly the same carry rule used for an array of digits, except a singly linked list makes the last node difficult to reach from the front.

Reverse the links temporarily so the least significant digit becomes the first node. The carry can then move through the list in the natural forward direction. After the addition, reverse the links again to restore most-significant-digit-first order. If every original digit was 9, the carry survives the final node, so a new leading node containing 1 is required.

Approach

1. 1Reverse the entire list and use the returned head, because the least significant digit must be visited first for the carry to be correct.
2. 2Set carry to 1 and walk from the reversed head while both the current node and carry exist, because once the carry becomes zero, all remaining digits are already unchanged.
3. 3Add carry to the current digit, store value modulo 10, and set carry to value divided by 10, because these two operations produce the digit and the carry for ordinary decimal addition.
4. 4When a carry remains after the last existing node, append a zero node before advancing, because the carry needs a node whose value it can turn into 1 without losing the original list structure.
5. 5Reverse the list again after the carry has finished, because the returned representation must remain most-significant-digit first.
6. 6If carry is still nonzero after the second reversal, create a node containing that carry and place it before the head, because inputs such as 9 or 99 need one extra leading digit.
7. 7Return the resulting head, which may be different from the original head only when a new leading node was created.

Complexitylinear work and constant working memory

Annotated solutionC++ · iterative reversal · constant extra space

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int value) : val(value), next(nullptr) {}
};

class Solution {
    ListNode* reverseList(ListNode* head) {
        ListNode* previous = nullptr;

        while (head != nullptr) {
            ListNode* nextNode = head->next;
            head->next = previous;
            previous = head;
            head = nextNode;
        }

        return previous;
    }

public:
    ListNode* addOne(ListNode* head) {
        head = reverseList(head);

        ListNode* current = head;
        int carry = 1;

        while (current != nullptr && carry != 0) {
            int value = current->val + carry;
            current->val = value % 10;
            carry = value / 10;

            if (carry != 0 && current->next == nullptr) {
                current->next = new ListNode(0);
            }

            current = current->next;
        }

        head = reverseList(head);

        if (carry != 0) {
            ListNode* first = new ListNode(carry);
            first->next = head;
            head = first;
        }

        return head;
    }
};

The append-zero line is what lets the same loop handle both ordinary carry propagation and an all-9 suffix. For example, after reversing 99, the last existing node becomes 0 with carry 1; appending a zero gives the carry a place to write 1. The later prepend handles the carry that remains only after every existing digit has become 0.

The one-pass alternativesame bounds, fewer link changes

You can avoid reversing the list by remembering the last node whose digit is not 9. Scan from the front, update that node by one, and turn every node after it into 0. Those later nodes are exactly the suffix that would have received the carry. If no such node exists, every digit is 9 and a new leading 1 is needed.

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int value) : val(value), next(nullptr) {}
};

class Solution {
public:
    ListNode* addOne(ListNode* head) {
        ListNode* lastNotNine = nullptr;
        ListNode* current = head;

        while (current != nullptr) {
            if (current->val != 9) {
                lastNotNine = current;
            }
            current = current->next;
        }

        if (lastNotNine == nullptr) {
            ListNode* first = new ListNode(1);
            first->next = head;
            head = first;
            lastNotNine = head;
        } else {
            ++lastNotNine->val;
        }

        current = lastNotNine->next;
        while (current != nullptr) {
            current->val = 0;
            current = current->next;
        }

        return head;
    }
};

This is a different arrangement rather than an asymptotic improvement: it is still O(n) time and O(1) extra space. It avoids two reversals and never changes links, which can make the code easier to reason about when link order must remain stable. The reverse-based version mirrors the carry process more directly and is a useful pattern whenever a singly linked list requires backward-style processing.

Common mistakestwo failures that can look correct on simple examples