Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int getLength(Node *Node){
- int size = 0;
- while (Node != NULL){
- Node = Node->next;
- size++;
- }
- return size;
- }
- Node* paddzeros(Node* sNode, int diff){
- if (sNode == NULL)
- return NULL;
- Node* zHead =new Node(0); //zHead will be head of new padded list
- diff--;
- Node* temp = zHead;
- while (diff--){
- temp->next =new Node(0);
- temp = temp->next;
- }
- temp->next = sNode;
- return zHead;
- }
- Node* subtractLinkedListHelper(Node* l1, Node* l2, bool& borrow){
- if (l1 == NULL && l2 == NULL && borrow == 0) return NULL;
- //if l1 exist,send l1 next else NULL same for l2 in recursion funciton.we are doing this because
- //we will subtract from back of the list
- Node* previous = subtractLinkedListHelper(l1 ? l1->next : NULL,l2 ? l2->next : NULL, borrow);
- int d1 = l1->data;
- int d2 = l2->data;
- int sub = 0;
- if (borrow){ //if borrow.decrease one from current node of big number
- d1--;
- borrow = false;
- }
- if (d1 < d2){ //if current node of big number is samller thant current node of small numer
- borrow = true; //borrow=true and add 10 with current node
- d1 = d1 + 10;
- }
- sub = d1 - d2;
- Node* current =new Node(sub); //make a node and assign current subtraction
- current->next = previous; //and point current subtracted node with previous node and return current
- return current;
- }
- Node* subLinkedList(Node* l1, Node* l2){
- if (!l1 && !l2) return NULL;
- while(l1){ //removing zeros at front that can give us wrong length of list
- if(l1->data!=0) break;
- l1=l1->next;
- }
- while(l2){ //removing zeros at front
- if(l2->data!=0) break;
- l2=l2->next;
- }
- if(!l1) return l2; //if one list is 0 or all zeros,then second list will be answer
- if(!l2) return l1;
- int len1 = getLength(l1); //find length of both linkedlist
- int len2 = getLength(l2);
- Node *lNode = NULL, *sNode = NULL;
- Node* temp1 = l1;
- Node* temp2 = l2;
- if (len1 != len2){ //if different length of both linkedlist means one list with high length is big.
- if(len1>len2){
- lNode=l1;
- sNode=l2;
- }
- else{
- lNode=l2;
- sNode=l1;
- }
- sNode = paddzeros(sNode, abs(len1 - len2)); //add 0 in smaller linkedlist at front
- }
- else{ //if length of both list is same,then start traversing from start of the number and compare
- while (l1 && l2){
- if (l1->data != l2->data){
- lNode = l1->data > l2->data ? temp1 : temp2;
- sNode = l1->data > l2->data ? temp2 : temp1;
- break;
- }
- l1 = l1->next;
- l2 = l2->next;
- }
- }
- if(!lNode && !sNode){ //If both list will be same,then lNode and sNode will be NULL,so return output 0.
- lNode=new Node(0); return lNode;
- }
- bool borrow = false; //initially borrow=0;
- Node *res=subtractLinkedListHelper(lNode, sNode, borrow);
- while(res){ //remove trailing zeros from output
- if(res->data!=0) return res;
- res=res->next;
- }
- return res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement