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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
