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.
Algorithm
- Create two singly linked list and store the values.
- Call Addstruct() function. Create head to keep track of starting node of the result. First, add 1’s digit/first node of both lists.
- Add the sum in the result list at the beginning.
- If any carry then pass that to the next addition.
- Increment the nodes and repeat the same procedure.
Program
[code lang=”c”]
#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
}
}
[/code]
You might also like…
Insert a node at a specific position in LinkedList