without sorting, it will be mess...O(n^2)
with recursion, it will be lot of stack space however since this is asked i
would do it this way
The only problem i see with this code is what if the lists are 1,2,1,2 AND
2,1,1,1
This code will give 2 common message twice and 1 common message 4 times
struct node* sortAndMerge(struct node *a, struct node *b)
{
if !a return b;
if !b return a;
struct node *result = NULL;
if (a->data <=b->data)
{ result =a; result->next = sortAndMerge(a->next, b);}
else { result =b; result->next = sortAndMerge(b->next, a);}
return result;
}
void merge(struct node **pL)
{
if (!(*pL) || !(*pL->next)) return NULL;
struct node *a=NULL;
struct node *b=NULL;
split(*pL, &a, &b);
merge(&a); merge(&b);
sortAndMerge(a,b);
}
void intersect(struct node *a, struct node *b)
{
if (!a) || (!b) return;
merge(&a);
merge(&b);
struct node * result = sortAndMerge(a,b);
struct node *current =result;
while (current)
{
if (current->data ==current->next->data) printf("%d ",
current->data);
current = current->next;
}
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 2:35 PM, Saurabh Koar <saurabhkoar...@gmail.com>wrote:
> I mean is it possible to solve the problem using recursion and without
> sorting? (in O(1) space and <O(n^2) complexity? ). As he didnt say
> anything,I am just clearing my doubts.
>
> --
> 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.
