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 2:     set:  current=head of 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;
}*head=NULL;
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;
   head=current;
   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;
   head=current;
   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;
   head=current;
   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();
    current=head;
    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;
   current=head;
   prevnode=NULL;
   while(current!=NULL)
   {
         nextnode=current->next;
         current->next=prevnode;
         prevnode=current;
         current=nextnode;
   }
   head=prevnode;
}
void print()
{
   struct node *current;
   current=head;
   while(current!=NULL)
   {
         printf("%d ",current->data);
         current=current->next;
   }
}

OUTPUT: