@Ashish
We can sort a list in another way as follows:
1) Recursively divide the list into two halves..
2) Call merge while joining the sorted lists..
MergeSort(node * p)
{
if ( p contains only one element)
return p;
p1 = MergeSort(first half of list pointed by p);
p2 = MergeSort(second half of list pointed by p);
return MergeSortedLLS(p1, p2);
}
Complexity of sorting:
To partition the list in 2 halves - O(N)
To merge 2 sorted list - O(N)
To sort:
T(N) = O(N) + T(N/2) + O(N)
= N log N
On Dec 31 2011, 4:46 pm, Lucifer <sourabhd2...@gmail.com> wrote:
> @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.
