Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<bits/stdc++.h>
- using namespace std;
- struct node{
- int data;
- node* next;
- };
- struct node* head1,head2;
- void insert(int data, node* head)
- {
- node* temp=new node;
- temp->data=data;
- temp->next=NULL;
- node* temp1=head;
- if(head==NULL)
- {
- head=temp;
- }
- else
- {
- while(temp1->next!=NULL)
- {
- temp1=temp1->next;
- }
- temp1->next=temp;
- }
- }
- node* add(node* l1,node* l2)
- {
- stack<int> s1, s2; // store digits in stack
- for (; l1; l1 = l1->next) s1.push(l1->data);
- for (; l2; l2 = l2->next) s2.push(l2->data);
- node* res = NULL; // res is head node of the resultant list
- node *temp, *prev = NULL;
- int carry = 0, sum;
- while( !s1.empty()|| !s2.empty())
- {
- if (!s1.empty())
- sum += s1.top(), s1.pop(); // get digit sum
- if (!s2.empty())
- sum += s2.top(), s2.pop();
- // update carry for next calulation
- carry = (sum >= 10)? 1 : 0;
- // update sum if it is greater than 10
- sum = sum % 10;
- node* temp=new node;
- temp->data=sum;
- temp->next=NULL;
- // if this is the first node then
- // set it as head of the resultant list
- if(res == NULL)
- res = temp;
- // If this is not the first
- // node then connect it to the rest.
- else
- prev->next = temp;
- // Set prev for next insertion
- prev = temp;
- // Move first and second pointers to next nodes
- if (l1) l1 = l1->next;
- if (l2) l2 = l2->next;
- }
- if (carry > 0) {
- node *newNode = new node;
- newNode->data = carry;
- newNode->next = NULL;
- temp->next =newNode;
- }
- // return head of the resultant list
- return res;
- }
- void print(node* head)
- {
- node* temp=new node;
- temp=head;
- while(temp!=NULL)
- {
- cout<<temp->data;
- temp=temp->next;
- }
- cout<<"\n";
- }
- int main()
- {
- int n;
- head1=NULL;
- head2=NULL;
- insert(3,head1);
- insert(2,head1);
- insert(1,head1);
- insert(1,head2);
- insert(0,head2);
- node* ans=add(head1,head2);
- print(ans);
- return 0;
- }
Add Comment
Please, Sign In to add comment