/**
* Definition for singlylinked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode *a,ListNode *b)
{
ListNode * temp;
if(!a)
return b;
if(!b)
return a;
if(a>val <=b>val)
{
temp=a;
temp>next=merge(a>next,b);
}
else
{ temp=b;
temp>next=merge(a,b>next);
}
return temp;
}
void half(ListNode *head , ListNode **a,ListNode **b)
{
ListNode *fast,*slow,*prev;
slow=fast=head;
while(fast && fast>next)
{
prev=slow;
slow=slow>next;
fast=fast>next>next;
}
*a=head;
*b=slow;
prev>next=NULL;
}
ListNode *sortList(ListNode *head) {
if(!head)
return NULL;
if(!head>next)
return head;
ListNode * a,*b;
half(head,&a,&b);
a=sortList(a);
b=sortList(b);
return merge(a,b);
}
};
ACCEPTED : mergesort cpp  auxillary space o(1)  time complexity o(nlongn)


Thanks @Shangrila , i have taken care of your note in my next post for nqueens solution. :)

I think it is O(nlogn) :
ListNode *sortList(ListNode *head) {
//called for every half of the list : height of tree, if each recursive call is treated as mother //child node = logn
if(!head) return NULL; if(!head>next) return head; ListNode * a,*b; half(head,&a,&b); // O(n) a=sortList(a); b=sortList(b); return merge(a,b); // O(n)
}
therefore : O(time for each level of the recursive call tree * no. of levels)
=O(n*logn)2)Auxillarys space complexity is O(1) : If you observe in the merge function,temp is just a reference pointer pointing to already allocated memory i.e. the parent list itself,their is no extra allocation of memory at all.
This is the reason i said auxillary space(space taken excluding the problem data space) is O(1) but space complexity(space taken including the problem data space) is still O(n) ,their is a difference between the both.Though in general when people talk about space complexity in algorithm analysis , people actually refer to the auxillary space complexity.

I think you are right about O(nlogn) as I didn't notice the recursive call of sortList(). However the auxiliary space complexity you are talking about seems meaningless as when we are considering complexity, we usually talk about the overall complexity other than partial complexity. of course, we get the overall complexity by accumulating the parts. therefore, the O(1) space mentioned by the problem is definitely overall complexity.

sorry I was wrong about space usage for merge function. the overall space complexity is O(logn) not because the temp pointer within merge function, it's actually because the two pointers, the head parameter and the return value within sortList function. every time the function is called, these data are pushed to the stack which takes up space.

after some search, I see that auxiliary space is space complexity minus space taken by the input. see this: http://functionspace.org/topic/241/Differencebetweenspacecomplexityandauxiliaryspace
therefore, auxiliary space used by your code is still O(n).

I have already mentioned the difference between auxiliary space and space complexity in my first comment.
I am not allocating new memory in any of the driver functions and neither is any space used up in the recursive stack because all that my recursive function is doing is to change pointer values.So auxiliary space is O(1).