Add 1 To Number Represented As Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a number represented in the form of a linked list, we are required to add 1 to it and report the answer as a linked list.

For Example: Given is a Number 19999 in the form of a linked list, and after adding 1 to it, it should give the result as follows:

Problem Statement Understanding

The problem statement is quite straightforward, we are provided with a number represented in the form of a [linked list](https://www.prepbytes.com/blog/linked-list/squarerootn-th-node-in-a-linked-list/ "linked list") which means we will be getting the head/root of the linked list as our argument, and we have to add 1 to the number represented in the form of a linked list.

Let's learn programming languages online and try to understand it more clearly using an example.

Let's assume we are given the number 19999. So the linked list will be :

  • Initial Linked List: 1 β†’ 9 β†’ 9 β†’ 9 β†’ 9
  • We will be getting the head pointing to the 1st node of the linked list, which is 1 as our argument.
  • So the head pointer will point to the first node:
    head β†’1 β†’ 9 β†’ 9 β†’ 9 β†’ 9
  • After Adding 1, our linked list will become:
    head β†’2 β†’ 0 β†’ 0 β†’ 0 β†’ 0
  • Which is the result after adding 1 to 19999 = 20000

At this point in time, we have understood the problem statement. Now try to formulate an approach for this problem.

Helpful Observation

  • Since we do an arithmetic operation starting from the one's place digit and then move towards the tenth place digit, hundredth place digit and so on, therefore we need to get hold of the one's place digit to add 1 to it.
  • Now the one's place digit is the last digit of our number given in the form of a linked list. But we cannot move backside in the Singly Linked List, as only the next pointer is given.
  • So we can reverse the linked list and do operations starting from the first node of the reversed linked list.
  • So, our original linked list will be reversed and thus we can now simply add 1 to the head of the linked list (maintaining carry). Finally, we will reverse the list again and will output it as our final linked list.

Approach and Algorithm

  • Reverse the given Linked List. For example, the given linked list is 1 β†’ 9 β†’ 9 β†’ 9 β†’ 9, after reversing it will become 9 β†’ 9 β†’ 9 β†’ 9 β†’ 1.
  • Start the linked list traversal, take 2 variable sum and carry.
  • The variable sum will hold the value at a particular place (node) and carry will take forward the carry from the previous sum given by (sum/10).
  • Now, since we are adding 1, the sum can be either equal than 10 or less than 10.
  • Therefore, carry will be 1 for a sum greater than 10 and 0 for a sum less than 10.
  • Keep moving forward in the list and store the appropriate value in the resultant list node given by sum%10.
  • At last, again reverse the linked list to get the output in the correct format.

Dry Run

For addOne Function

Code Implementation

#include
using namespace std;
class Node
{
public:
    int data;
    Node *next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};
Node* addOne(Node* head_ref)
{
    Node* res = head_ref; // res will point to the head of the resultant list.


    int carry = 1 , sum;//Why carry is taken as 1 ? => because we need to add 1

    Node* prev; // prev pointer is necessary for the last node, if at last carry is there, we need to add a new Node with value carry.
    // (Take example of 9->9->9->9)

    while (head_ref != NULL) {
        sum = carry + head_ref->data;

        carry = (sum >= 10) ? 1 : 0;

        head_ref->data = (sum % 10);

        prev = head_ref;
        head_ref = head_ref->next;

    }
    if (carry > 0) {
        prev->next = new Node(carry);
    }

    return res;
}
Node*  reverseList(Node* head_ref) {
    Node* curr = head_ref;
    Node* prev = NULL, *next;

    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}
Node* addOneToList(Node* head_ref)
{
    head_ref = reverseList(head_ref);

    head_ref = addOne(head_ref);

    head_ref = reverseList(head_ref);

    return head_ref;
}

void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{
    Node* head = new Node(1);
    head->next = new Node(9);
    head->next->next = new Node(9);
    head->next->next->next = new Node(9);
    head->next->next->next->next = new Node(9);

    head = addOneToList(head);
    printList(head);
    return 0;
}

Output

2 β†’ 0 β†’ 0 β†’ 0 β†’ 0

Time Complexity: O(n), Overall we are doing a total of 3 passes, 2 for reversing and 1 while adding, where n is the number of nodes in the given LinkedList.
Space complexity: O(1), constant space complexity, as no extra space is used.

Can we Do Any Better ?

  • Now we have seen that for the above approach to work, we need to reverse the list twice. So we are doing two extra traversals worth O(N) complexity.
  • However, if we observe carefully, we will see that it is the digit 9 which makes all the changes, for all other digits we just need to increment by 1. But in the case of 9 carry comes into the picture and modifies the whole list.
  • So, we can try targeting the digit 9 itself. We don't need to reverse the linked list.

Approach and Algorithm

We will find the last node which is not 9. Now for this, there can be 3 scenarios:

  • Case1: If there exists no node which is not 9, it means every node is 9. For example 9->9->9->9. In such a case we will make every node value equal to 0 and add a new node with value 1 at the front of the list.
  • Case2: If the last node of the list is not 9, then simply increment the value of last node by 1.
  • Case3: If the node which is not 9 is somewhere in the middle, and after that, every node is 9. For example 1299, then in such cases increment the last non-nine node by 1 and make all nodes right to it as zero. So 1299 becomes 1300.

We will take 2 pointers, one for storing the last node which is not 9, other for traversing the list. Then handle each case independently.

Dry Run

Code Implementation

#include
using namespace std;
class Node
{
public:
    int data;
    Node *next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
Node* addOneToList(Node* head)
{
    Node* last = NULL , *current_node = head;

    //Through this loop we will find the last non-nine node.
    while (current_node->next != NULL)
    {
        if (current_node->data != 9) {
            last = current_node;
        }
        current_node = current_node->next;
    }


    //This loop will run till the second last node, so for the last node we will check using if condition.
    //If the last node itself is not 9. Then simply increment the value by 1 and return the head.
    if (current_node->data != 9) {
        current_node->data++;
        return head;
    }

    //After loop if last is still NULL, that means there is no value which is not 9.
    //For example 9->9->9->9
    if (last == NULL) {
        //1 extra node will be needed.
        last = new Node(1);
        last->next = head;
        head = last;

        //then make every node 0
        last = last->next;
        while (last != NULL) {
            last->data = 0;
            last = last->next;
        }
        return head;
    }

    //Last case => when the non-nine node is somewhere in middle;
    // we will increment the value and make everything right to it as 0
    last->data++;
    last = last->next;
    while (last != NULL) {
        last->data = 0;
        last = last->next;
    }
    return head;
}
int main()
{
    Node* head = new Node(1);
    head->next = new Node(9);
    head->next->next = new Node(9);
    head->next->next->next = new Node(9);
    head->next->next->next->next = new Node(9);

    head = addOneToList(head);
    printList(head);
    return 0;
}

Output

2 β†’ 0 β†’ 0 β†’ 0 β†’ 0

Time Complexity: O(n) only single pass, where n is the number of nodes in the given LinkedList.

This blog tried to discuss the problem when we are given a number in the form of a linked list and we need to add 1 to it. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post ArrayList and LinkedList remove() methods in Java with Examples
Next post Insert a node into the middle of the linked list

Leave a Reply

Your email address will not be published. Required fields are marked *