Program to add two numbers represented as List

Program to add two numbers represented as List

Question

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a program to add two numbers and return the sum as a linked list.

 

Logic

  • The logic is simple. We have to traverse the lists and add the corresponding nodes.
  • If we get a carry then pass that to the next addition.
  • There are four possibilities for the addition. You can see that in the program.
  • Store the result in a list and print that.

adding node gif

Algorithm

  1. Create two singly linked list and store the values.
  2. Call Addstruct() function. Create head to keep track of starting node of the result. First, add 1’s digit/first node of both lists.
  3. Add the sum in the result list at the beginning.
  4. If any carry then pass that to the next addition.
  5. Increment the nodes and repeat the same procedure.

Program

#include<stdio.h>
#include<stdlib.h>
/*Creating structure*/
 struct node
{
    int data;
    struct node* next;                  //link to next node in list
};
/*Creating new node*/
 struct node* create(int data)
 {
     struct node* temp = NULL;
     temp = (struct node*)malloc(sizeof(struct node)); //intializing pointer
     temp->data = data;
     temp->next = NULL;
     return temp;                       //passing the node address
 }
 struct node* Addstruct(struct node* A,struct node* B)
 {
     int carry 0;						//To keep track of carry for each digit
     int store = 0;						//To store the sum 

     struct node* head = (struct node*)malloc(sizeof(struct node));//creating memory location
     head = create(0);					//intialize with node->data = 0;

     /*  loop  runs until all the digits added*/
     while(A!=NULL || B!=NULL)
     {
         struct node* temp = (struct node*)malloc(sizeof(struct node));
         temp = create(0);
         /* when both have data EX: 
          53
         +17  
         in this A->data = 3 and B->data = 7 then execute this if statement*/
         if(A!=NULL && B!= NULL)
         {
             store = (A->data + B->data + carry)%10;
             pass = (A->data + B->data + carry)/10;
             A = A->next;
             B = B->next;

         }
         /*when only A have data EX: 
          17
         + 5     
          In this A->data =1 but we don't have data in B*/ 
          else if(A!=NULL &&  B == NULL)
         {
             store = (A->data + carry)%10;
             pass = (A->data + carry)/10;
             A = A->next;

         }
         /*when only B have data Ex:
          5
        +17
         In this B->data = 1 but no data in A*/

         else if(A==NULL && B!= NULL)
         {
             store =(B->data +carry)%10;
             pass = (B->data +carry)/10;
             B = B->next;
         }

        addatbeg(&head,store);			//Add the node at the beginning of list 

     }
     /* if we carry left after sum EX:
     12
    +92  =104
     In this 9 + 2 gives 10 with carry 1 so add that at beginning of list*/ 
     if(carry != 0)
       {
         addatbeg(&head,carry);

       }

    return head;						//return the head(starting node) of the list 
 }
 void addatbeg(struct node**q , int num)
 {
     struct node* temp;
      temp =(struct node*)malloc(sizeof(struct node));
       temp->data = num;				//assign data
       temp->next = *q;					
       *q = temp;                       //Make the new node as head

 }

int main()
{
    struct node* nodeA = (struct node*)malloc(sizeof(struct node));
    struct node* nodeB = (struct node*)malloc(sizeof(struct node));
    
	/*input from Sample_1*/
    nodeA = create(3);
    nodeA->next = create(1);
    nodeA->next->next = create(6);

    nodeB = create(2);
    nodeB->next = create(0);
    nodeB->next->next = create(3);
    
    struct node* nodeC = (struct node*)malloc(sizeof(struct node));
    nodeC = Addstruct(nodeA, nodeB);

    /*printing the total by traversing the list*/
    while(nodeC->next !=NULL)
     {
         printf("%d",nodeC->data);
         nodeC = nodeC->next;                           //Increment node pointer
     }

}

You might also like…

Insert a node at a specific position in LinkedList

 

 

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x