Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Add 1 to a number represented as linked list

MEDIUMProblemSolveExternal Links

Description

You are given a singly linked list where each node stores a single digit between 0 and 9. The digits are arranged from the most significant digit at the head to the least significant digit at the tail, together forming a non-negative integer.

Your task is to add 1 to the number represented by this linked list and return the head of the modified linked list.

The main challenge arises when adding 1 causes a carry that propagates through multiple digits. For example, adding 1 to the list 1 → 9 → 9 (representing 199) produces 2 → 0 → 0 (representing 200). In the extreme case where every digit is 9, a brand-new node must be inserted at the front of the list to accommodate the extra digit.

Examples

Example 1

Input: head = 4 → 5 → 6

Output: 4 → 5 → 7

Explanation: The linked list represents the number 456. Adding 1 gives 457. Only the last digit changes from 6 to 7 because 6 + 1 = 7, which does not produce a carry.

Example 2

Input: head = 1 → 9 → 9

Output: 2 → 0 → 0

Explanation: The linked list represents 199. Adding 1 gives 200. The last digit 9 + 1 = 10, which sets it to 0 and carries 1 to the next digit. That digit is also 9, so 9 + 1 = 10 again — it becomes 0 with another carry. Finally, the first digit 1 + 1 = 2, and the carry stops.

Example 3

Input: head = 9 → 9 → 9

Output: 1 → 0 → 0 → 0

Explanation: The linked list represents 999. Adding 1 gives 1000. Every digit overflows to 0, and the carry propagates all the way past the head. A new node with value 1 must be prepended, making the list one node longer than the original.

Constraints

  • 1 ≤ length of linked list ≤ 10^5
  • 0 ≤ node.data ≤ 9

Editorial

Brute Force

Intuition

When you add numbers by hand, you start from the rightmost digit and work left, carrying over any overflow. The linked list stores digits from left to right (most significant first), so we cannot directly start from the last digit.

Recursion offers a natural solution: if we make a recursive call that dives all the way to the end of the list first, we can handle the addition on the way back out. Think of it like walking to the end of a hallway before turning around — the last room you visit is the least significant digit, which is exactly where addition should begin.

Each recursive call returns a carry value. The deepest call returns carry = 1 (since we are adding 1). As the recursion unwinds, each node adds the incoming carry to its own digit, keeps the ones place, and passes any new carry upward. If carry is still 1 after the head node is processed, a new node with value 1 is prepended to the list.

Step-by-Step Explanation

Let's trace through with head = 1 → 9 → 9 (representing 199):

Step 1: Begin recursion at node 0 (value 1). We cannot add yet — we must reach the end of the list first. Recurse to the next node.

Step 2: Now at node 1 (value 9). Still not at the end. Recurse deeper to node 2.

Step 3: Now at node 2 (value 9). This is the last node — its next pointer is null. Recurse once more; the call on null returns carry = 1.

Step 4: Back at node 2. Add the returned carry to this digit: 9 + 1 = 10. Set this node's digit to 10 % 10 = 0. Compute outgoing carry = 10 / 10 = 1. Return carry = 1.

Step 5: Back at node 1 (value 9). Incoming carry is 1. Compute 9 + 1 = 10. Set digit to 0, outgoing carry = 1. Return carry = 1.

Step 6: Back at node 0 (value 1). Incoming carry is 1. Compute 1 + 1 = 2. Set digit to 2, outgoing carry = 0.

Step 7: Recursion fully unwound. The final carry is 0, so no new head node is needed. The modified list is 2 → 0 → 0, representing 200.

Recursive Carry Propagation on 1 → 9 → 9 — Watch how recursion dives to the tail of the list first, then propagates carry back toward the head as each call returns.

Algorithm

  1. Define a helper function addWithCarry(node) that recurses to the end of the list.
  2. Base case: if node is null, return carry = 1 (we are adding 1).
  3. Recursive step: call addWithCarry(node.next) to get the carry from the rest of the list.
  4. Compute sum = node.data + carry.
  5. Update node.data = sum % 10.
  6. Return sum / 10 as the new carry.
  7. After the helper returns to the main function, check if carry is still non-zero.
  8. If carry > 0, create a new node with that carry value and prepend it as the new head.

Code

class Solution {
public:
    int addWithCarry(Node* node) {
        if (node == nullptr) {
            return 1;
        }

        int sum = node->data + addWithCarry(node->next);
        node->data = sum % 10;
        return sum / 10;
    }

    Node* addOne(Node* head) {
        int carry = addWithCarry(head);

        if (carry > 0) {
            Node* newHead = new Node(carry);
            newHead->next = head;
            head = newHead;
        }

        return head;
    }
};
class Solution:
    def addOne(self, head):
        carry = self._addWithCarry(head)

        if carry > 0:
            new_head = Node(carry)
            new_head.next = head
            head = new_head

        return head

    def _addWithCarry(self, node):
        if node is None:
            return 1

        total = node.data + self._addWithCarry(node.next)
        node.data = total % 10
        return total // 10
class Solution {
    public Node addOne(Node head) {
        int carry = addWithCarry(head);

        if (carry > 0) {
            Node newHead = new Node(carry);
            newHead.next = head;
            head = newHead;
        }

        return head;
    }

    private int addWithCarry(Node node) {
        if (node == null) {
            return 1;
        }

        int sum = node.data + addWithCarry(node.next);
        node.data = sum % 10;
        return sum / 10;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once during the recursive descent and once during the unwinding phase. Each visit performs O(1) arithmetic (addition, modulo, division). Therefore the total work is proportional to the number of nodes, giving O(n).

Space Complexity: O(n)

The recursion creates one stack frame per node. In the worst case (all nodes), the call stack grows to depth n. For a list with up to 10^5 nodes, this can be a significant amount of memory and risks a stack overflow in environments with limited stack size.

Why This Approach Is Not Efficient

The recursive approach achieves O(n) time, which is already optimal — every node must be inspected at least once. However, it uses O(n) auxiliary space due to the recursion stack.

With the constraint that the list can contain up to 10^5 nodes, the recursive approach builds a call stack 10^5 frames deep. Many runtime environments set a default stack size between 1 MB and 8 MB, and each stack frame for this function holds at least a pointer, an integer, and a return address. At 10^5 frames, this is borderline — some systems will handle it, but others will throw a stack overflow error.

More fundamentally, the O(n) extra space is unnecessary. The only information flowing backward through the list is a single integer (the carry), which is always 0 or 1. We should be able to process the list using O(1) additional space if we can find a way to iterate from the least significant digit without recursion.

Key insight: if we reverse the linked list first, the least significant digit moves to the head. We can then iterate forward (head to tail), propagating carry with a simple loop — no recursion, no stack, no extra space.

Optimal Approach - Reverse and Add

Intuition

Imagine you have a row of numbered cards laid out on a table from left to right: the leftmost card is the most significant digit and the rightmost is the least significant. To add 1, you would naturally flip the rightmost card first. But in a singly linked list you can only walk forward — you cannot easily go backward.

The trick is to flip the entire row of cards around so that the rightmost card is now on the left. Now you can walk left to right (forward) and add 1 starting from what was originally the last digit. After finishing the addition, flip the row back to restore the original order.

Concretely, the algorithm has three phases:

  1. Reverse the linked list so the least significant digit becomes the head.
  2. Add 1 from the new head, propagating carry forward through the reversed list.
  3. Reverse the list again to restore the most-significant-first ordering.

This approach visits each node a constant number of times and uses only a handful of pointer variables — no recursion stack, no auxiliary array, no extra data structure.

Step-by-Step Explanation

Let's trace through with head = 1 → 9 → 9 (representing 199):

Step 1: Reverse the list. The list becomes 9 → 9 → 1. Now the ones digit (9) is at the head.

Step 2: Initialize carry = 1. Start at the head of the reversed list (value 9). Compute 9 + 1 = 10. Set this digit to 10 % 10 = 0. New carry = 10 / 10 = 1.

Step 3: Move to the next node (value 9). Add carry: 9 + 1 = 10. Set digit to 0, carry = 1. The carry continues to propagate.

Step 4: Move to the next node (value 1). Add carry: 1 + 1 = 2. Set digit to 2, carry = 0. The carry has been fully absorbed.

Step 5: Carry is 0 and we have processed all necessary nodes. The reversed list is now 0 → 0 → 2.

Step 6: Reverse the list back to restore the original digit order. The final list is 2 → 0 → 0, representing 200.

Reverse, Add 1, Reverse Back — Tracing 1 → 9 → 9 — Watch the three-phase process: reverse the list to expose the least significant digit, propagate carry forward, then reverse back to restore order.

Algorithm

  1. Reverse the linked list using the standard iterative three-pointer technique (prev, curr, next).
  2. Initialize carry = 1 (since we are adding 1).
  3. Traverse the reversed list from head to tail:
    • Compute sum = curr.data + carry
    • Set curr.data = sum % 10
    • Update carry = sum / 10
    • If carry becomes 0, stop early — no further nodes need to change
  4. If carry is still 1 after traversing all nodes, create a new node with value 1 and append it to the end of the reversed list.
  5. Reverse the list again to restore the original most-significant-first ordering.
  6. Return the new head.

Code

class Solution {
public:
    Node* reverse(Node* head) {
        Node* prev = nullptr;
        Node* curr = head;
        while (curr != nullptr) {
            Node* nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }

    Node* addOne(Node* head) {
        // Step 1: Reverse the list
        head = reverse(head);

        // Step 2: Add 1 with carry propagation
        Node* curr = head;
        int carry = 1;
        Node* prev = nullptr;

        while (curr != nullptr && carry > 0) {
            int sum = curr->data + carry;
            curr->data = sum % 10;
            carry = sum / 10;
            prev = curr;
            curr = curr->next;
        }

        // Step 3: If carry remains, add a new node
        if (carry > 0) {
            prev->next = new Node(carry);
        }

        // Step 4: Reverse back to original order
        head = reverse(head);
        return head;
    }
};
class Solution:
    def addOne(self, head):
        # Step 1: Reverse the list
        head = self._reverse(head)

        # Step 2: Add 1 with carry propagation
        curr = head
        carry = 1
        prev = None

        while curr and carry > 0:
            total = curr.data + carry
            curr.data = total % 10
            carry = total // 10
            prev = curr
            curr = curr.next

        # Step 3: If carry remains, add a new node
        if carry > 0:
            prev.next = Node(carry)

        # Step 4: Reverse back to original order
        head = self._reverse(head)
        return head

    def _reverse(self, head):
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev
class Solution {
    public Node addOne(Node head) {
        // Step 1: Reverse the list
        head = reverse(head);

        // Step 2: Add 1 with carry propagation
        Node curr = head;
        int carry = 1;
        Node prev = null;

        while (curr != null && carry > 0) {
            int sum = curr.data + carry;
            curr.data = sum % 10;
            carry = sum / 10;
            prev = curr;
            curr = curr.next;
        }

        // Step 3: If carry remains, add a new node
        if (carry > 0) {
            prev.next = new Node(carry);
        }

        // Step 4: Reverse back to original order
        head = reverse(head);
        return head;
    }

    private Node reverse(Node head) {
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

Complexity Analysis

Time Complexity: O(n)

The algorithm performs three linear passes over the list: one to reverse, one to add with carry propagation, and one to reverse back. Each pass visits at most n nodes and does O(1) work per node. Total: 3 × O(n) = O(n).

Note: the addition pass often terminates early. If the last digit is not 9, carry becomes 0 after the first node and the loop stops immediately. The worst case (all 9s) still requires visiting every node.

Space Complexity: O(1)

We use only a fixed number of pointer variables (prev, curr, nxt) and one integer (carry). The reversal is done in-place by relinking existing nodes — no new nodes are created except in the all-9s case where exactly one new node is needed for the leading 1. This is a dramatic improvement over the recursive approach's O(n) stack space.