Advertisement
imashutosh51

Subtraction in Linked List

Jul 31st, 2022
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1. int getLength(Node *Node){
  2.     int size = 0;
  3.     while (Node != NULL){
  4.         Node = Node->next;
  5.         size++;
  6.     }
  7.     return size;
  8. }
  9.  
  10. Node* paddzeros(Node* sNode, int diff){
  11.     if (sNode == NULL)
  12.         return NULL;
  13.     Node* zHead =new Node(0);  //zHead will be head of new padded list
  14.     diff--;
  15.     Node* temp = zHead;
  16.     while (diff--){
  17.         temp->next =new Node(0);
  18.         temp = temp->next;
  19.     }
  20.     temp->next = sNode;
  21.     return zHead;
  22. }
  23.  
  24. Node* subtractLinkedListHelper(Node* l1, Node* l2, bool& borrow){
  25.     if (l1 == NULL && l2 == NULL && borrow == 0) return NULL;
  26.     //if l1 exist,send l1 next else NULL same for l2 in recursion funciton.we are doing this because
  27.     //we will subtract from back of the list
  28.     Node* previous = subtractLinkedListHelper(l1 ? l1->next : NULL,l2 ? l2->next : NULL, borrow);  
  29.    
  30.     int d1 = l1->data;
  31.     int d2 = l2->data;
  32.     int sub = 0;
  33.     if (borrow){    //if borrow.decrease one from current node of big number
  34.         d1--;
  35.         borrow = false;
  36.     }
  37.     if (d1 < d2){    //if current node of big number is samller thant current node of small numer
  38.         borrow = true;  //borrow=true and add 10  with current node
  39.         d1 = d1 + 10;
  40.     }
  41.     sub = d1 - d2;
  42.     Node* current =new Node(sub);  //make a node and assign current subtraction
  43.     current->next = previous;     //and point current subtracted node with previous node and return current
  44.     return current;
  45. }
  46.  
  47. Node* subLinkedList(Node* l1, Node* l2){
  48.     if (!l1 && !l2) return NULL;
  49.     while(l1){    //removing zeros at front that can give us wrong length of list
  50.         if(l1->data!=0) break;
  51.         l1=l1->next;
  52.     }
  53.     while(l2){     //removing zeros at front
  54.         if(l2->data!=0) break;
  55.         l2=l2->next;
  56.     }
  57.    
  58.     if(!l1) return l2;   //if one list is 0 or all zeros,then second list will be answer
  59.     if(!l2) return l1;  
  60.    
  61.     int len1 = getLength(l1);  //find length of both linkedlist
  62.     int len2 = getLength(l2);
  63.    
  64.     Node *lNode = NULL, *sNode = NULL;
  65.     Node* temp1 = l1;
  66.     Node* temp2 = l2;
  67.    
  68.     if (len1 != len2){  //if different length of both linkedlist means one list with high length is big.
  69.         if(len1>len2){
  70.             lNode=l1;
  71.             sNode=l2;
  72.         }
  73.         else{
  74.             lNode=l2;
  75.             sNode=l1;
  76.         }
  77.         sNode = paddzeros(sNode, abs(len1 - len2)); //add 0 in smaller linkedlist at front
  78.     }
  79.     else{              //if length of both list is same,then start traversing from start of the number and compare
  80.         while (l1 && l2){
  81.             if (l1->data != l2->data){
  82.                 lNode = l1->data > l2->data ? temp1 : temp2;
  83.                 sNode = l1->data > l2->data ? temp2 : temp1;
  84.                 break;
  85.             }
  86.             l1 = l1->next;
  87.             l2 = l2->next;
  88.         }
  89.     }
  90.    
  91.     if(!lNode && !sNode){     //If both list will be same,then lNode and sNode will be NULL,so return output 0.
  92.         lNode=new Node(0); return lNode;
  93.     }
  94.    
  95.     bool borrow = false;  //initially borrow=0;
  96.     Node *res=subtractLinkedListHelper(lNode, sNode, borrow);
  97.    
  98.     while(res){               //remove trailing zeros from output
  99.         if(res->data!=0) return res;
  100.         res=res->next;
  101.     }
  102.    
  103.     return res;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement