Sort a linked list in O(n log n) time using constant space complexity.
分析：排序算法中，堆排序、归并排序、快速排序、希尔排序的时间复杂度是nlogn，堆排序和归并排序对下标依赖性比较强，比较适合顺序表的排序，对链表处理起来比较复杂。希尔排序用的比较少。所以我选择的是快速排序，结果是正确的，但时间超出限制了。如果有大神做过同样的题目，跪求告知解法~~~~
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partion(ListNode* head,ListNode* start,ListNode* end,ListNode** newEnd)
{
int key=end->val;
ListNode* pre=start;
ListNode* behind=start;
*newEnd=behind;
while(pre!=end)
{
if(pre->val < key)
{
if(pre!=behind)
{
int tmp=pre->val;
pre->val=behind->val;
behind->val=tmp;
}
*newEnd=behind;
behind=behind->next;
}
pre=pre->next;
}
int tmp=pre->val;
pre->val=behind->val;
behind->val=tmp;
return behind;
}
void qSort(ListNode* head,ListNode* start,ListNode* end)
{
if(start!=end)
{
ListNode* newEnd=NULL;
ListNode* mid=partion(head,start,end,&newEnd);
if(mid!=end)
qSort(head,mid->next,end);
qSort(head,start,newEnd);
}
}
ListNode* sortList(ListNode* head) {
if(head==NULL)
return NULL;
ListNode* p=head;
while(p->next)
p=p->next;
qSort(head,head,p);
return head;
}
};