Guest User

soln

a guest
May 30th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. struct node{
  5. int data;
  6. node* next;
  7. };
  8. struct node* head1,head2;
  9.  
  10. void insert(int data, node* head)
  11. {
  12. node* temp=new node;
  13. temp->data=data;
  14. temp->next=NULL;
  15. node* temp1=head;
  16.  
  17. if(head==NULL)
  18. {
  19. head=temp;
  20. }
  21. else
  22. {
  23. while(temp1->next!=NULL)
  24. {
  25. temp1=temp1->next;
  26. }
  27. temp1->next=temp;
  28. }
  29.  
  30.  
  31.  
  32. }
  33. node* add(node* l1,node* l2)
  34. {
  35.  
  36. stack<int> s1, s2; // store digits in stack
  37.  
  38. for (; l1; l1 = l1->next) s1.push(l1->data);
  39. for (; l2; l2 = l2->next) s2.push(l2->data);
  40.  
  41. node* res = NULL; // res is head node of the resultant list
  42. node *temp, *prev = NULL;
  43. int carry = 0, sum;
  44.  
  45. while( !s1.empty()|| !s2.empty())
  46. {
  47. if (!s1.empty())
  48. sum += s1.top(), s1.pop(); // get digit sum
  49.  
  50. if (!s2.empty())
  51. sum += s2.top(), s2.pop();
  52.  
  53. // update carry for next calulation
  54. carry = (sum >= 10)? 1 : 0;
  55.  
  56. // update sum if it is greater than 10
  57. sum = sum % 10;
  58.  
  59. node* temp=new node;
  60. temp->data=sum;
  61. temp->next=NULL;
  62.  
  63. // if this is the first node then
  64. // set it as head of the resultant list
  65. if(res == NULL)
  66. res = temp;
  67.  
  68. // If this is not the first
  69. // node then connect it to the rest.
  70. else
  71. prev->next = temp;
  72.  
  73. // Set prev for next insertion
  74. prev = temp;
  75.  
  76. // Move first and second pointers to next nodes
  77. if (l1) l1 = l1->next;
  78. if (l2) l2 = l2->next;
  79.  
  80.  
  81.  
  82.  
  83. }
  84.  
  85.  
  86. if (carry > 0) {
  87. node *newNode = new node;
  88. newNode->data = carry;
  89. newNode->next = NULL;
  90. temp->next =newNode;
  91. }
  92.  
  93.  
  94. // return head of the resultant list
  95. return res;
  96.  
  97. }
  98.  
  99. void print(node* head)
  100. {
  101. node* temp=new node;
  102. temp=head;
  103. while(temp!=NULL)
  104. {
  105. cout<<temp->data;
  106. temp=temp->next;
  107. }
  108. cout<<"\n";
  109.  
  110. }
  111. int main()
  112. {
  113. int n;
  114. head1=NULL;
  115. head2=NULL;
  116.  
  117. insert(3,head1);
  118. insert(2,head1);
  119. insert(1,head1);
  120.  
  121. insert(1,head2);
  122. insert(0,head2);
  123.  
  124. node* ans=add(head1,head2);
  125. print(ans);
  126.  
  127. return 0;
  128. }
Add Comment
Please, Sign In to add comment