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 <rajn...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.