merge two linked list without sorting them, the resultant list should be
sorted one...
any other better solution?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, Jan 12, 2011 at 3:15 PM, Ashish Goel <ashg...@gmail.com> wrote:
> 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 algogeeks@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.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
