# C Program to increment a number by 1 represented by Linked List in O(n) time.

In this question, a number which is represented by Linked List is given to you. You have to increment the number by 1 and the number must remain in the form of Linked List.

For example: if number is 23 then Linked List representation is like:-  2->3, where two is the first node contain the address of the second node in which data field is 3.

ex 1:   if the number is  2 3 0 , then updated linked list after incrementation should be 2 3 1
ex 2:   if the number is  2 9 9 , then updated linked list after incrementation should be 3 0 0
ex 3:   if the number is     9 9 , then updated linked list after incrementation should be  1 0 0

Algorithm to increment a number by 1 represented by Linked List in O(n) time:

step 1:     Reverse the Linked List
step 3:     do while    current!=NULL:
step 4:                 if current.data<9:
step 5:                             current.data=current.data+1
step 6:                             break
step 7:                 else if  current.data=9 && current.next!=NULL:
step 8:                             current.data=0
step 9:                             current=current.next
step 10:              else if  current.data=9 && current.next=NULL
step 11:                           current.data=0
step 12:                           current.next= Create new node of struct node type
step 13:                           current=current.next
step 14:                           current.data=1
step 15:                           current.next=NULL
step 16:                           current=current.next
step 17:   EndWhile
step 18:   Reverse Linked List again

PROGRAM:

```#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
void reverse();
void print();
void increment();
int main()
{

struct node *current;

printf("\nExample 1:\n");

current=(struct node*)malloc(sizeof(struct node));
current->data=9;
current->next=NULL;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=9;
current->next=NULL;

printf("\nNumber represented by Linked List before incrementation: \n");
print();
increment();
printf("\n\nNumber represented by Linked List after incrementation:\n");
print();

/*Generating Example 2*/

printf("\n\nExample 2:\n");
current=(struct node*)malloc(sizeof(struct node));
current->data=1;
current->next=NULL;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=4;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=9;
current->next=NULL;

printf("\nNumber represented by Linked List before incrementation: \n");
print();
increment();
printf("\n\nNumber represented by Linked List after incrementation:\n");
print();

/*Generating Example 3*/

printf("\n\nExample 3:\n");
current=(struct node*)malloc(sizeof(struct node));
current->data=1;
current->next=NULL;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=4;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=3;
current->next=NULL;

printf("\nNumber represented by Linked List before incrementation: \n");
print();
increment();
printf("\n\nNumber represented by Linked List after incrementation:\n");
print();
return 0;

}
void increment()
{
struct node *current,*temp;
int carry;
reverse();
while(current!=NULL)
{
if(current->data<9)
{
current->data=current->data+1;
break;
}
else if(current->data==9 && current->next!=NULL )
{
current->data=0;
current=current->next;
}
else if(current->data==9 && current->next==NULL)
{
current->data=0;
current->next=(struct node*)malloc(sizeof(struct node));
current=current->next;
current->data=1;
current->next=NULL;
current=current->next;
}
}
reverse();
}
void  reverse()
{
struct node *current,*prevnode,*nextnode;
prevnode=NULL;
while(current!=NULL)
{
nextnode=current->next;
current->next=prevnode;
prevnode=current;
current=nextnode;
}
}
void print()
{
struct node *current;