@Ashish..
I have something in mind.. but would require verification by u..
Lets say, the structure of the data node is as follows:
struct node
{
int data;
struct node *next;
};
Now, given 2 sorted linked lists we can right a O(N) time and in-place
merge process, to build a sorted merged linked list...
I am not putting down the code for the merge process because that's
not the goal of the algo given below..
Lets call it:
node * MergeSortedLLS(node *p1, node*p2)
// here p1 and p2 are the head pointers of the 2 sorted lists..
// The return value is the head of the merged sorted list...
Now, say the lists are named as L1 and L2...
If we are not given the no. of elements in L1 and L2.. then we can
traverse both the lists and get the individual counts...
Say the no. of nodes in L1 and L2 are N1 and N2
The below cited algorithm is nothing but the application of mergesort
on a singly linked list rather than an array with slight
modification...
node* Merge2UnsortedLists(node *L1, node* L2, int N1, int N2)
{
node * p1 = MergeSortLL( &L1, 0, N1 -1 );
node * p2 = MergeSortLL( &L2, 0, N2 -1 );
return MergeSortedLLS(p1, p2);
}
node * MergeSort(node ** p, int start, int end)
{
node * head = *p;
if (start == end)
*p = (*p)->next;
else
{
int mid = (start + end)/2;
node * p1 = MergeSort(p, start, mid);
node * p2 = MergeSort(p, mid + 1, end);
head = MergeSortedLLS(p1, p2);
}
return head;
}
/*
Call : Merge2UnsortedLists(L1, L2, N1, N2);
*/
The above is in-place..
Time complexity:
MergeSortedLLS - N
MergeSort - NLogN
Merge2UnsortedLists - N1LogN1(2 sort the L1) + N2LogN2 (to sort L2) +
N1 + N2 ( to merge : sorted L1 and L2)
--------------------------------------
Let me know what do u think...
On 31 Dec, 14:27, Ashish Goel <ashg...@gmail.com> wrote:
> 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.
