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
#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