make use of two ptr approach.first traverse the first linkd list and fnd k th element from last where k is the length of subrahend then perform subtraction.
On Wed, Aug 25, 2010 at 8:18 PM, Raj N <[email protected]> wrote: > My approach: > Use divide and conquer approach. i.e divide(a) divide(b) i.e first list and > divide(c) divide(d) of second list recursively (like mergesort). Then apply > subtract(a,c) and subtract(b,d) > > It goes this way: > Make both lists of equal length by appending 0s at the beginning of smaller > list. Assuming list1 > list2 > struct node > { > int data; > struct node *next; > }; > > void divide(struct node* root1,struct node *root2) > { > struct node *a; > struct node *b; > struct node *c; > struct node *d; > struct node *result; > int borrow=0; > > if(root1==NULL || root1->next==NULL) > return; > else > { > split(root1,&a,&b); > split(root2,&c,&d); > } > if(b->next==NULL && a->next==NULL) > { > subtract(b,d,&borrow,&result); > subtract(a,c,&borrow,&result); > } > } > > void split(struct node* source, struct node **front, struct node **back) > { > struct node *slow, *fast; > slow=source; > fast=source->next; > > while(fast!=NULL) > { > fast=fast->next; > if(fast!=NULL) > { > slow=slow->next; > fast=fast->next; > } > } > *front=source; > *back=slow->next; > slow->next=NULL; > } > > void subtract(struct node *n1, struct node *n2, int *borrow,struct node > **result) > { > *result=(struct node*)malloc(sizeof(struct node)); > if(n1->data >= n2->data && !borrow) > { > result->data = n1->data - n2->data; > > } > else if(n1->data > n2->data && borrow) > { > result->data = (n1->data-1) - n2->data; > borrow = 0; > } > else if(n1->data < n2->data && !borrow) > { > result->data = (n1->data + 10) - n2->data; > borrow=1; > } > else if(n1->data <= n2->data && borrow) > { > result->data = (n1->data+9) - n2->data; > } > > // Insert the new node result at the beginning of result list > } > > Tell me if there're any corrections !! > > > On Wed, Aug 25, 2010 at 3:24 PM, Raj N <[email protected]> wrote: > >> Input : Two large singly linked lists representing numbers with most >> significant digit as head and least significant as last node. >> Output: Difference between the numbers as a third linked list with >> Most significant digit as the head. >> Eg: >> --- >> Input: >> A = 5->4->2->0->0->9->0->0 >> B = 1->9->9 >> Output: >> C = 5->4->2->0->0->7->0->1 >> Required complexity : >> O(n) >> Constraint: >> Reversing linked list is NOT allowed >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
