☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Add one to a number represented by LL

Medium TUF ID 617 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A non-negative integer is stored in a singly linked list, one decimal digit per node, with the most significant digit at the head. Add one to the number and return the head of the resulting list. The input has no leading zeros except for the number 0 itself. If the input list is empty we treat it as the number 0, so the answer is a single node holding 1.

Constraints: 1 ≤ n ≤ 10^5 digits, each 0 ≤ val ≤ 9. The number can have far more digits than fit in a long, so converting the whole list to an integer is not an option.

Example 1

head = 1 -> 2 -> 3
answer = 1 -> 2 -> 4          // 123 + 1 = 124

Example 2

head = 9 -> 9 -> 9
answer = 1 -> 0 -> 0 -> 0     // 999 + 1 = 1000, the list grows by one node

Example 3

head = 1 -> 9 -> 9
answer = 2 -> 0 -> 0          // the carry travels left until it meets a digit that is not 9

Approach 1: Brute force, reverse, add, reverse back

Intuition. Pen-and-paper addition starts from the units digit and moves left, but a singly linked list can only be walked from the head, which is the most significant digit. The simplest fix is to make the list point the other way: reverse it, so the units digit is the head, perform the schoolbook addition with a carry, and reverse it back. Three linear passes, no extra memory.

Algorithm.

  1. If the list is empty return a single node 1.
  2. Reverse the list in place.
  3. Set carry = 1 and walk from the (new) head. At each node compute sum = val + carry, store sum % 10 and set carry = sum / 10. Stop as soon as the carry becomes 0, since nothing further changes.
  4. If the walk ran off the end with carry still 1, every digit was a 9; append a new node holding 1 after the last node. Remember the list is still reversed at this point, so appending at the tail is correct.
  5. Reverse the list again and return its head.
static ListNode bruteForce(ListNode head) {
    if (head == null) return new ListNode(1);          // an empty list stands for 0
    head = reverse(head);
    int carry = 1;                                     // the +1 we are adding
    ListNode cur = head, last = null;
    while (cur != null && carry > 0) {
        int sum = cur.val + carry;
        cur.val = sum % 10;
        carry = sum / 10;
        last = cur;
        cur = cur.next;
    }
    if (carry > 0) last.next = new ListNode(carry);    // every digit was 9: append the new most significant digit (the list is still reversed)
    return reverse(head);
}

The reversal helper is the standard three-pointer loop.

static ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Complexity. Time O(n): two reversals and one addition pass, each linear. Space O(1): a handful of pointers, plus at most one new node.

Why is last guaranteed to be non-null when we append? The loop runs at least once because the list is non-empty and carry starts at 1, so last always points at a real node, and when carry survives the loop it is the final node.

Approach 2: Better, recursion carries the result back up

Intuition. Reversing twice works but feels heavy for what is a single carry propagation. Recursion gives us the right-to-left order for free: a call that descends to the end of the list and does its work after the recursive call returns processes the units digit first, then the tens, and so on, exactly like the written addition. The value a call returns is the carry into the digit to its left.

Algorithm.

  1. addOneRec(node): if node is null, return 1. This is the “+1” entering the units digit.
  2. Otherwise let carry = addOneRec(node.next), compute sum = node.val + carry, store sum % 10 in the node and return sum / 10.
  3. In the wrapper, call addOneRec(head). If the returned carry is 0 return head; otherwise create a new node holding the carry and make it the new head.
static ListNode better(ListNode head) {
    if (head == null) return new ListNode(1);
    int carry = addOneRec(head);
    if (carry == 0) return head;
    return new ListNode(carry, head);                  // the carry out of the first digit becomes a new leading node
}

static int addOneRec(ListNode node) {
    if (node == null) return 1;                        // base case: the "+1" arrives at the units digit
    int carry = addOneRec(node.next);
    int sum = node.val + carry;
    node.val = sum % 10;
    return sum / 10;
}

Complexity. Time O(n): every node is visited once on the way down and once on the way up. Space O(n) for the recursion stack, one frame per digit.

The recursive version is the cleanest to read, but the stack depth equals the number of digits. With 10^5 nodes that is close to the default Java stack limit, which is a real risk in a judge. It also does strictly more work than necessary: once a digit below 9 absorbs the carry, every frame above it still does an addition of 0.

Approach 3: Optimal, one forward pass

Intuition. Look at what adding one actually does to the digits. Scanning from the right, every trailing 9 becomes 0, and the first digit that is not 9 goes up by one. Nothing to the left of that digit changes. So the whole operation is determined by the rightmost digit that is not 9. We can find it in a single left-to-right pass by remembering the most recent non-9 node we have seen: when the pass ends, that remembered node is the rightmost one. Increment it, zero everything after it, done. If no such node exists the number is all 9s, and the answer is a 1 followed by n zeros.

Algorithm.

  1. If the list is empty return a single node 1.
  2. Walk the list once; whenever cur.val != 9, set lastNotNine = cur.
  3. If lastNotNine is still null, insert a new node with value 0 in front of the head and let lastNotNine point at it. It plays the role of a leading zero that is about to be incremented.
  4. Increment lastNotNine.val.
  5. Set every node after lastNotNine to 0.
  6. Return the head (which may be the newly inserted node).
static ListNode optimal(ListNode head) {
    if (head == null) return new ListNode(1);
    ListNode lastNotNine = null;
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (cur.val != 9) lastNotNine = cur;
    }
    if (lastNotNine == null) {                         // every digit is 9: 99...9 + 1 = 100...0
        lastNotNine = new ListNode(0, head);           // a leading 0 that is about to become the new 1
        head = lastNotNine;
    }
    lastNotNine.val++;
    for (ListNode cur = lastNotNine.next; cur != null; cur = cur.next) cur.val = 0;
    return head;
}

Dry run on head = 2 -> 9 -> 0 -> 9:

step cur.val lastNotNine
scan 2 node(2)
scan 9 node(2)
scan 0 node(0)
scan 9 node(0)
increment   node(0) becomes 1
zero the rest   node(9) after it becomes 0

Result: 2 -> 9 -> 1 -> 0, which is 2909 + 1 = 2910. The 9 to the left of the incremented digit was never touched, exactly as in written arithmetic.

Complexity. Time O(n): one scan plus the zeroing pass, which only covers the trailing 9s. Space O(1): one extra pointer and at most one new node. No reversal, no recursion.

Edge cases and pitfalls