Friday, August 16, 2013

Adding two numbers using Singly Linked List

This program has asked many times in Amazon written..... Addition of two number's using singly linked list.
// A simple solution would be ..... easy to follow the below program.
Example:- n1=1 2 3
                n2=5 6 7 8
              ouptut would be  5 8 0 1

#include <stdio.h>
#include <stdlib.h>

typedef struct LinkList
{
    int data;
    struct LinkList *next;
}List;

void CreateList(List **Head,int value)
{
    List *ptr=NULL,*node=(List*)malloc(sizeof(List));
    node->data=value;
    node->next=NULL;
    if(*Head==NULL)
    *Head=node;
    else
     {ptr=*Head;
      while(ptr->next)
      ptr=ptr->next;
      ptr->next=node;
       
     }
}
void AddLL(List **Head,List *Head1,List *Head2)
{
    int sum=0,h1=0,h2=0;
    List *node=NULL,*ptr=NULL;
   Reverse(&Head1);Reverse(&Head2);
     while(Head1!=NULL||Head2!=NULL||sum>0)
     {   h1=0;h2=0;
         if(Head1!=NULL)
         {h1=Head1->data;Head1=Head1->next;}
         if(Head2!=NULL)
         {h2=Head2->data;Head2=Head2->next;}
         sum+=h1+h2;
         node=(List *)malloc(sizeof(List));
         node->data=sum%10;
         node->next=NULL;
         sum/=10;
         if(*Head==NULL)
         {
             *Head=node;
             ptr=*Head;
         }
         else
         {
             ptr->next=node;
             ptr=ptr->next;
         }
     }

Reverse(Head);
}

void Reverse(List **Head)
{
 List *temp=NULL,*ptr=*Head,*prev=NULL;
 if(!ptr)return;
 while(ptr->next!=NULL)
 {
     temp=ptr->next;
     ptr->next=prev;
     prev=ptr;
     ptr=temp;
 }
 ptr->next=prev;
 *Head=ptr;
}

void Display(List *ptr)
{
    if(!ptr)return;
    printf("%d ",ptr->data);
    Display(ptr->next);
}
main()
{
List *Head=NULL,*Head1=NULL,*Head2=NULL;
int i=0,value,n;
printf("Enter the length of digit of first no.\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
 scanf("%d",&value);
 CreateList(&Head1,value);
}
printf("\nEnter the length of digit of first no.\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
 scanf("%d",&value);
 CreateList(&Head2,value);
}
printf("\n");
AddLL(&Head,Head1,Head2);
Display(Head);
return 0;
}

No comments:

Post a Comment