@Sharad: Ya that's fine. But the problem says msb is at the head of the
list. So you've to start subtraction from the end of the list and you don't
have previous pointer. Thats the main challenge, also you can't reverse !!
The only thing that came to my mind was divide and conquer approach and
extract every node and perform subtraction.
On Wed, Aug 25, 2010 at 9:45 PM, sharad kumar <aryansmit3...@gmail.com>wrote:
> 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 <rajn...@gmail.com> 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 <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<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 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.
