Linked List: Add 1 to the linked list

Problem Statement:

You are given an linked list, you need to add one to it and return as result.

Example

Example 1:

Input: 1 -> 9 -> 9
Output: 2 -> 0 -> 0

Input: 9 -> 9 -> 9
Output: 1 -> 0 -> 0 -> 0

Solution

Before we solve this problem, there are 2 cases that we need to check.

Case 1: Where all the numbers are 999. Adding 1 to it will become 1000.

Case 2: Where the last number is 9. i.e 889 adding 1 to it will become 890.

Keeping above two cases we shall start solving the problem.

We take 2 pointers, “prev” and “curr”.

We traverse the list using “curr” pointer and “prev” pointer will point to the rightmost digit that is less than 9.

If the “prev” node is NULL, it means that the digits are all 9, in that case, we need to take a new node as the digits will be increased.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

#include<iostream>
#include<vector>

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}


Node* add_one(Node* head)
{
 
    // to store the last node that is not equal to 9
    Node* perv = NULL;
    Node* cur = head;
 
    // traverse till last node
    while (cur->next != NULL) 
    {
 
        if (cur->data != 9) 
        {
            perv = cur;
        }
        cur = cur->next;
    }
 
    // if the last node is not 9, then just increment it and return
    if (cur->data != 9) 
    {
        cur->data++;
        return head;
    }
 
    // if prev is null, it means the LL is of type 9 -> 9 -> 9 ->
    if (perv == NULL) 
    {
        perv = new Node();
        perv->data = 0;
        perv->next = head;
        head = perv;
    }
 

    perv->data++;
    perv = perv->next;
 
    while (perv != NULL) 
    {
        perv->data = 0;
        perv = perv->next;
    }
 
    return head;
}
 

   int main()
{
    struct Node *list_1 = NULL; 
    
    insert_at_begenning(&list_1,1);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,1);

    printf("Original List\n");
    display_list(&list_1);

    add_one(list_1);
    printf("The result list is\n");
    
    display_list(&list_1);

    return 0;
}

Output:

Original List 
1 -> 2 -> 3 -> 1 
The result list is 
1 -> 2 -> 3 -> 2