Add 1 to a Linked List Number

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Add 1 to number stored in linked list. Reverse list, add 1 with carry, reverse back. Or recursively carry from end.

Algorithm

1Recursive: add 1 to last node. If sum >= 10: carry = 1, node.val = 0. Propagate carry back.
2If carry remains after head: insert new node with value 1 at front.

Common Pitfalls

•Reverse-add-reverse is simpler iteratively. Recursive carry propagation is cleaner but uses O(n) stack.

Add 1 to a Linked List Number.java

Java

// Approach: Reverse the linked list, add 1 with carry propagation, then reverse again.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

class Solution {
    public Node addOne(Node head) {
        Node num = reverse(head);
        Node rev = num;

        int sum = num.data + 1;
        int carry = sum / 10;
        num.data = sum % 10;

        while (carry > 0) {
            if (num.next == null)
                num.next = new Node(0);

            num = num.next;
            sum = num.data + carry;
            num.data = sum % 10;
            carry = sum / 10;
        }

        return reverse(rev);
    }

    Node reverse(Node head) {
        if (head == null || head.next == null)
            return head;

        Node prev = null;
        Node curr = head;
        Node next = null;

        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}

Was this solution helpful?