jayati

Add two numbers represented by linked lists

Oct 10th, 2023
1,283
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  1. //{ Driver Code Starts
  2. // driver
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. /* Linked list Node */
  8. struct Node {
  9.     int data;
  10.     struct Node* next;
  11.     Node(int x) {
  12.         data = x;
  13.         next = NULL;
  14.     }
  15. };
  16.  
  17. struct Node* buildList(int size)
  18. {
  19.     int val;
  20.     cin>> val;
  21.    
  22.     Node* head = new Node(val);
  23.     Node* tail = head;
  24.    
  25.     for(int i=0; i<size-1; i++)
  26.     {
  27.         cin>> val;
  28.         tail->next = new Node(val);
  29.         tail = tail->next;
  30.     }
  31.    
  32.     return head;
  33. }
  34.  
  35. void printList(Node* n)
  36. {
  37.     while(n)
  38.     {
  39.         cout<< n->data << " ";
  40.         n = n->next;
  41.     }
  42.     cout<< endl;
  43. }
  44.  
  45.  
  46. // } Driver Code Ends
  47. /* node for linked list:
  48.  
  49. struct Node {
  50.     int data;
  51.     struct Node* next;
  52.     Node(int x) {
  53.         data = x;
  54.         next = NULL;
  55.     }
  56. };
  57.  
  58. */
  59.  
  60. class Solution
  61. {
  62.     public:
  63.     //Function to add two numbers represented by linked list.
  64.     struct Node* reverse(struct Node* head){
  65.         if(head==NULL){
  66.             return head;
  67.         }
  68.         Node *prev=NULL;
  69.         Node *curr=head;
  70.         Node *nextptr;
  71.         while(curr!=NULL){
  72.             nextptr=curr->next;
  73.             curr->next=prev;
  74.            
  75.             prev=curr;
  76.             curr=nextptr;
  77.         }
  78.         return prev;
  79.     }
  80.     struct Node* addTwoLists(struct Node* first, struct Node* second)
  81.     {
  82.         // code here
  83.         Node* l1=reverse(first);
  84.         Node* l2=reverse(second);
  85.        
  86.         Node* head = new Node(-1);
  87.         Node* temp=head;
  88.        
  89.        
  90.         int carr=0;
  91.         while(l1!=NULL || l2!=NULL || carr)
  92.         {
  93.            int sum=0;
  94.            if(l1!=NULL)
  95.            {
  96.                sum+=l1->data;
  97.                l1=l1->next;
  98.            }
  99.            if(l2!=NULL)
  100.            {
  101.                sum+=l2->data;
  102.                l2=l2->next;
  103.            }
  104.            sum+=carr;
  105.            carr=sum/10;
  106.            Node* newNode= new Node(sum%10);
  107.            temp->next=newNode;
  108.            temp=temp->next;
  109.            
  110.         }
  111.         return reverse(head->next);
  112.     }
  113. };
  114.  
  115.  
  116. //{ Driver Code Starts.
  117.  
  118. int main()
  119. {
  120.     int t;
  121.     cin>>t;
  122.     while(t--)
  123.     {
  124.         int n, m;
  125.        
  126.         cin>>n;
  127.         Node* first = buildList(n);
  128.        
  129.         cin>>m;
  130.         Node* second = buildList(m);
  131.         Solution ob;
  132.         Node* res = ob.addTwoLists(first,second);
  133.         printList(res);
  134.     }
  135.     return 0;
  136. }
  137.  
  138. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment