# Add 1 to a number represented as a linked list

## Given a number which is represented in linked list, write a functio that will add 1 to the number

### Example

INPUT
8->4->5 //Number is 845

OUTPUT
8->4->6 //After adding 1 the number is 846

## Algorithm

1. Reverse the given linked list

2. traverse the reversed linked list, add 1 to the first node(ie, sum = 1 + newhead->data). Insert the sum in result linked list(insert at beginning).

3. If the sum is greater than 10, then insert (sum - 10) to the result and update carry(ie, carry =1) for the next calculation.

4. print result

## C++ Program

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

struct LLNode{
int data;
LLNode *next;
};
//Protype
// Function to reverse the linked list //
{
LLNode * prev   = NULL;
LLNode * current = head;
LLNode * next;
while (current != NULL)
{
next  = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
// Adds one to the number which is represented in list
{
LLNode* result = NULL; // result is head node of the resultant list
LLNode *temp, *prev = NULL;
int carry = 1, sum;

while (newhead != NULL) //Till list becomes empty
{
//Next didgit is the sum of carry and current digit
sum = carry + newhead->data;

// update carry for next calulation
// update sum if it is greater than 10
if (sum>=10)
{
sum = sum - 10;
carry = 1;
}
else
carry =0;
//Inserting sum at the begining of result
insertAtBeginning(&result, sum);
}

if (carry > 0)
insertAtBeginning(&result, carry);

// return head of the resultant list
return result;
}

{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{
LLNode *result = NULL;
LLNode *head = NULL; //initial list has no elements

cout<<"Number represented by list is 845"<<endl;

cout<<"After adding 1 to the number"<<endl;
display(&result);
return 0;
}

### Method 2

In this method there is no need to reverse the linked list. We will use recursion

## Algorithm

1. Recursively reach last node and forward carry to previous nodes

2. At the end end if there is a carry, then just insert carry at the begining of the list.

## C++ Program

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

struct LLNode{
int data;
LLNode *next;
};
//Protype
// Recursively add 1 from end to beginning and returns
// carry after all nodes are processed.
{
// If linked list is empty, then
// return carry
if (head == NULL)
return 1;

// Add carry returned be next node call

// Update data and return new carry
head->data = (res) % 10;
return (res) / 10;
}

// This function mainly uses addWithCarry().
{
// Add 1 to linked list from end to beginning

//if there is a carray at end. add carry to the list
if (carry)
{
}

}

// The main function that adds two linked lists represented by list1 and list2.
// The sum of two lists is stored in a list referred by result

{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{
LLNode *result = NULL;
LLNode *head = NULL; //initial list has no elements

cout<<"Number represented by list is 845"<<endl;