imashutosh51

Subtraction in Linked List

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