Add one to a number represented by LL

Intuition

Imagine you have a number represented as a linked list, where each node contains a single digit. The first node contains the leftmost digit. Our goal is to add one to this number. This might sound simple, but we need to handle the digit carry-over, just like we do when adding numbers manually. Starting from the rightmost digit makes it easier to manage carry-overs. However, since our linked list starts from the leftmost digit, we need to reverse the list first. This makes it easier to add one from the least significant digit and manage any carry-over.

Approach

Reverse the Linked List: Reverse the linked list so we can start the addition from the rightmost digit.
Add One: Add one to the first digit of the reversed list. If there’s a carry (result is 10), set the current digit to 0 and carry over 1 to the next digit.
Handle the Carry: If there’s still a carry after reaching the end of the list, add a new node with the digit 1.
Reverse Again: Reverse the list again to restore the original order, now with the added value.
Return the New Head: Return the head of the modified linked list.

Dry Run

Without Carry

With Carry

#include <bits/stdc++.h>
using namespace std;

//Definition of
//Single linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    //Function to reverse the linked list
    ListNode* reverseList(ListNode* head) {
        // Initialize pointers
        ListNode* prev = NULL;
        ListNode* current = head;
        ListNode* next = NULL;
        
        while (current != NULL) {
            // Store next node
            next = current->next;
            // Reverse the link
            current->next = prev;
            // Move prev to current
            prev = current;
            // Move current to next
            current = next;
        }
        
        return prev;
    }
    //Function to add one to Linked List
    ListNode *addOne(ListNode *head) {
        //Reverse the linked list
        head = reverseList(head);
        
        //Create a dummy node
        ListNode* current = head;
        //Initialize carry with 1
        int carry = 1;  
        
        while (current != NULL) {
            /*Sum the current node's value 
            and the carry*/
            int sum = current->val + carry;
            //Update carry
            carry = sum / 10;
            //Update the node's value
            current->val = sum % 10;
            
            /*If no carry left
            break the loop*/
            if (carry == 0) {
                break;
            }
            
            /*If we've reached the end of the list
            there's still a carry,
            add a new node with the carry value*/
            if (current->next == NULL && carry != 0) {
                current->next = new ListNode(carry);
                break;
            }
            
            // Move to the next node
            current = current->next;
        }
        
        // Reverse the list 
        head = reverseList(head);
        
        // New head
        return head;
    }
};

//Function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    //Creation of Linked List
    ListNode* head1 = new ListNode(1);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(3);

    //Solution instance
    Solution solution;
    head1 = solution.addOne(head1);
    cout << "Result after adding one: ";
    printList(head1);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode() {
        val = 0;
        next = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to reverse the linked list
    public ListNode reverseList(ListNode head) {
        // Initialize pointers
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;
        
        while (current != null) {
            // Store next node
            next = current.next;
            // Reverse the link
            current.next = prev;
            // Move prev to current
            prev = current;
            // Move current to next
            current = next;
        }
        
        return prev;
    }
    
    // Function to add one to Linked List
    public ListNode addOne(ListNode head) {
        // Reverse the linked list
        head = reverseList(head);
        
        // Create a dummy node
        ListNode current = head;
        // Initialize carry with 1
        int carry = 1;  
        
        while (current != null) {
            /* Sum the current node's value 
            and the carry */
            int sum = current.val + carry;
            // Update carry
            carry = sum / 10;
            // Update the node's value
            current.val = sum % 10;
            
            /* If no carry left
            break the loop */
            if (carry == 0) {
                break;
            }
            
            /* If we've reached the end of the list
            and there's still a carry,
            add a new node with the carry value */
            if (current.next == null && carry != 0) {
                current.next = new ListNode(carry);
                break;
            }
            
            // Move to the next node
            current = current.next;
        }
        
        // Reverse the list 
        head = reverseList(head);
        
        // New head
        return head;
    }
}

// Function to print the linked list
public static void printList(ListNode head) {
    while (head != null) {
        System.out.print(head.val + " ");
        head = head.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    // Creation of Linked List
    ListNode head1 = new ListNode(1);
    head1.next = new ListNode(2);
    head1.next.next = new ListNode(3);

    // Solution instance
    Solution solution = new Solution();
    head1 = solution.addOne(head1);
    System.out.print("Result after adding one: ");
    printList(head1);
}
# Definition of singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to reverse the linked list
    def reverseList(self, head: ListNode) -> ListNode:
        # Initialize pointers
        prev = None
        current = head
        next = None
        
        while current is not None:
            # Store next node
            next = current.next
            # Reverse the link
            current.next = prev
            # Move prev to current
            prev = current
            # Move current to next
            current = next
        
        return prev
    
    # Function to add one to Linked List
    def addOne(self, head: ListNode) -> ListNode:
        # Reverse the linked list
        head = self.reverseList(head)
        
        # Create a dummy node
        current = head
        # Initialize carry with 1
        carry = 1  
        
        while current is not None:
            # Sum the current node's value and the carry
            sum = current.val + carry
            # Update carry
            carry = sum // 10
            # Update the node's value
            current.val = sum % 10
            
            # If no carry left, break the loop
            if carry == 0:
                break
            
            # If we've reached the end of the list and there's still a carry,
            # add a new node with the carry value
            if current.next is None and carry != 0:
                current.next = ListNode(carry)
                break
            
            # Move to the next node
            current = current.next
        
        # Reverse the list 
        head = self.reverseList(head)
        
        # New head
        return head

# Function to print the linked list
def printList(head: ListNode):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Creation of Linked List
    head1 = ListNode(1)
    head1.next = ListNode(2)
    head1.next.next = ListNode(3)

    # Solution instance
    solution = Solution()
    head1 = solution.addOne(head1)
    print("Result after adding one: ", end="")
    printList(head1)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to reverse the linked list
    reverseList(head) {
        // Initialize pointers
        let prev = null;
        let current = head;
        let next = null;
        
        while (current !== null) {
            // Store next node
            next = current.next;
            // Reverse the link
            current.next = prev;
            // Move prev to current
            prev = current;
            // Move current to next
            current = next;
        }
        
        return prev;
    }
    
    // Function to add one to Linked List
    addOne(head) {
        // Reverse the linked list
        head = this.reverseList(head);
        
        // Create a dummy node
        let current = head;
        // Initialize carry with 1
        let carry = 1;  
        
        while (current !== null) {
            // Sum the current node's value and the carry
            let sum = current.val + carry;
            // Update carry
            carry = Math.floor(sum / 10);
            // Update the node's value
            current.val = sum % 10;
            
            // If no carry left, break the loop
            if (carry === 0) {
                break;
            }
            
            // If we've reached the end of the list and there's still a carry,
            // add a new node with the carry value
            if (current.next === null && carry !== 0) {
                current.next = new ListNode(carry);
                break;
            }
            
            // Move to the next node
            current = current.next;
        }
        
        // Reverse the list 
        head = this.reverseList(head);
        
        // New head
        return head;
    }
}

// Function to print the linked list
function printList(head) {
    while (head !== null) {
        process.stdout.write(head.val + " ");
        head = head.next;
    }
    console.log();
}

// Creation of Linked List
let head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);

// Solution instance
const solution = new Solution();
head1 = solution.addOne(head1);
console.log("Result after adding one: ");
printList(head1);

Complexity Analysis

Time Complexity: O(N) because we traverse the linked list three times, each with a time complexity of O(N), resulting in O(3N), which simplifies to O(N) since constant factors are ignored in Big-O notation. Here, N is the number of nodes in the linked list. Space Complexity: O(1) because we use a constant amount of extra space for pointers and variables.

Intuition

When adding one to a number represented as a linked list, think of it as the process of incrementing the least significant digit (the last node) and propagating any carry to the more significant digits (the previous nodes). This process is similar to the manual addition we do with pen and paper. Starting from the least significant digit, if there is a carry (i.e., the digit becomes 10 after addition), set the current digit to 0 and move the carry to the next significant digit. If there's still a carry after processing the most significant digit (the head of the list), we need to add a new node to the front of the list to accommodate the carry.

Approach

To add one to a number represented as a linked list, we use a recursive function addHelper. This function traverses the list to the end, with the base case being when the current node is NULL, returning a carry of 1 to signify adding one to the number.
During each recursive call, we add the carry returned by the next node to the current node's value. If the current node's value is less than 10, no further carry is needed, so we return 0. If the value is 10 or more, we set the current node's value to 0 and return a carry of 1 to be added to the next significant digit.
After processing all nodes, we check if there's a carry left. If there is, we create a new node with a value of 1 and set it as the new head of the list. This handles cases where an additional digit is needed, like converting 999 into 1000.

Dry Run

For a detailed dry run, refer to the video.

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(NULL) {}
    ListNode(int data1) : val(data1), next(NULL) {}
    ListNode(int data1, ListNode *next1) : val(data1), next(next1) {}
};

class Solution {
public:
    // Helper function to add one to the linked list
    int addHelper(ListNode* temp) {
        /*If the list is empty
        return a carry of 1*/
        if(temp == NULL) 
            return 1;
        /*Recursively call addHelper 
        For the next node*/
        int carry = addHelper(temp->next); 
        /*Add the carry 
        to the current node's value*/
        temp->val += carry; 
        /*If the current node's value 
        is less than 10
        no further carry is needed*/
        if(temp->val < 10) 
            return 0;
       /* If the current node's value is 10 or more
        set it to 0 and return a carry of 1*/
        temp->val = 0; 
        return 1;
    }

    ListNode *addOne(ListNode *head) {
        /*Call the helper function 
        to start the addition process*/
        int carry = addHelper(head);
        /*If there is a carry left 
        after processing all nodes
        add a new node at the head */
        if(carry == 1) { 
            ListNode* newNode = new ListNode(1);
            /*Link the new node to the current head*/
            newNode->next = head; 
            /*Update the head to the new node*/
            head = newNode; 
        }
        // Return the head 
        return head; 
    }
};

//Function to print the linked list
void printLinkedList(ListNode* head) {
    ListNode* temp = head;
    // Traverse the linked list and print each node's value
    while (temp != nullptr) { 
        std::cout << temp->val << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

int main() {
    //Create a linked list with values 9, 9, 9 (999 + 1 = 1000)
    ListNode* head = new ListNode(9);
    head->next = new ListNode(9);
    head->next->next = new ListNode(9);

    //Print the original linked list
    cout << "Original Linked List: ";
    printLinkedList(head);

    //Add one to the linked list
    Solution sol;
    head = sol.addOne(head);

    //Print the modified linked list
    cout << "Linked List after adding one: ";
    printLinkedList(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode() {
        val = 0;
        next = null;
    }
    ListNode(int data1) {
        val = data1;
        next = null;
    }
    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Helper function to add one to the linked list
    private int addHelper(ListNode temp) {
        /* If the list is empty
        return a carry of 1 */
        if (temp == null) 
            return 1;
        
        /* Recursively call addHelper 
        For the next node */
        int carry = addHelper(temp.next); 
        
        /* Add the carry 
        to the current node's value */
        temp.val += carry; 
        
        /* If the current node's value 
        is less than 10
        no further carry is needed */
        if (temp.val < 10) 
            return 0;
        
        /* If the current node's value is 10 or more
        set it to 0 and return a carry of 1 */
        temp.val = 0; 
        return 1;
    }

    public ListNode addOne(ListNode head) {
        /* Call the helper function 
        to start the addition process */
        int carry = addHelper(head);
        
        /* If there is a carry left 
        after processing all nodes
        add a new node at the head */
        if (carry == 1) { 
            ListNode newNode = new ListNode(1);
            /* Link the new node to the current head */
            newNode.next = head; 
            /* Update the head to the new node */
            head = newNode; 
        }
        // Return the head 
        return head; 
    }
}

// Function to print the linked list
public static void printLinkedList(ListNode head) {
    ListNode temp = head;
    // Traverse the linked list and print each node's value
    while (temp != null) { 
        System.out.print(temp.val + " ");
        temp = temp.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    // Create a linked list with values 9, 9, 9 (999 + 1 = 1000)
    ListNode head = new ListNode(9);
    head.next = new ListNode(9);
    head.next.next = new ListNode(9);

    // Print the original linked list
    System.out.print("Original Linked List: ");
    printLinkedList(head);

    // Add one to the linked list
    Solution sol = new Solution();
    head = sol.addOne(head);

    // Print the modified linked list
    System.out.print("Linked List after adding one: ");
    printLinkedList(head);
}
# Definition of singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Helper function to add one to the linked list
    def addHelper(self, temp: ListNode) -> int:
        ''' If the list is empty
        return a carry of 1 '''
        if temp is None:
            return 1
        
        ''' Recursively call addHelper 
        For the next node '''
        carry = self.addHelper(temp.next)
        
        ''' Add the carry 
        to the current node's value '''
        temp.val += carry
        
        ''' If the current node's value 
        is less than 10
        no further carry is needed '''
        if temp.val < 10:
            return 0
        
        ''' If the current node's value is 10 or more
        set it to 0 and return a carry of 1 '''
        temp.val = 0
        return 1

    def addOne(self, head: ListNode) -> ListNode:
        ''' Call the helper function 
        to start the addition process '''
        carry = self.addHelper(head)
        
        ''' If there is a carry left 
        after processing all nodes
        add a new node at the head '''
        if carry == 1:
            newNode = ListNode(1)
            ''' Link the new node to the current head '''
            newNode.next = head
            ''' Update the head to the new node '''
            head = newNode
        # Return the head 
        return head

# Function to print the linked list
def printLinkedList(head: ListNode):
    temp = head
    # Traverse the linked list and print each node's value
    while temp:
        print(temp.val, end=" ")
        temp = temp.next
    print()

if __name__ == "__main__":
    # Create a linked list with values 9, 9, 9 (999 + 1 = 1000)
    head = ListNode(9)
    head.next = ListNode(9)
    head.next.next = ListNode(9)

    # Print the original linked list
    print("Original Linked List: ", end="")
    printLinkedList(head)

    # Add one to the linked list
    solution = Solution()
    head = solution.addOne(head)

    # Print the modified linked list
    print("Linked List after adding one: ", end="")
    printLinkedList(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Helper function to add one to the linked list
    addHelper(temp) {
        /* If the list is empty
        return a carry of 1 */
        if (temp === null) 
            return 1;
        
        /* Recursively call addHelper 
        For the next node */
        let carry = this.addHelper(temp.next);
        
        /* Add the carry 
        to the current node's value */
        temp.val += carry;
        
        /* If the current node's value 
        is less than 10
        no further carry is needed */
        if (temp.val < 10) 
            return 0;
        
        /* If the current node's value is 10 or more
        set it to 0 and return a carry of 1 */
        temp.val = 0;
        return 1;
    }

    addOne(head) {
        /* Call the helper function 
        to start the addition process */
        let carry = this.addHelper(head);
        
        /* If there is a carry left 
        after processing all nodes
        add a new node at the head */
        if (carry === 1) {
            let newNode = new ListNode(1);
            /* Link the new node to the current head */
            newNode.next = head;
            /* Update the head to the new node */
            head = newNode;
        }
        // Return the head 
        return head;
    }
}

// Function to print the linked list
function printLinkedList(head) {
    let temp = head;
    // Traverse the linked list and print each node's value
    while (temp !== null) {
        process.stdout.write(temp.val + " ");
        temp = temp.next;
    }
    console.log();
}

// Create a linked list with values 9, 9, 9 (999 + 1 = 1000)
let head = new ListNode(9);
head.next = new ListNode(9);
head.next.next = new ListNode(9);

// Print the original linked list
console.log("Original Linked List: ");
printLinkedList(head);

// Add one to the linked list
const solution = new Solution();
head = solution.addOne(head);

// Print the modified linked list
console.log("Linked List after adding one: ");
printLinkedList(head);

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the linked list. This is because each node in the linked list is visited exactly once by the recursive addHelper function. The process involves traversing the entire list to reach the end, and then propagating the carry back through each node, resulting in a linear time complexity of O(N). Space Complexity: O(N), due to the recursion stack. Since the addHelper function calls itself recursively for each node in the list, the maximum depth of the recursion stack is N, where N is the number of nodes in the linked list. This means the space required for the recursion stack grows linearly with the size of the list, leading to a space complexity of O(N).

Problem List

Add one to a number represented by LL

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code