谁说快排不行
链表排序
http://www.nowcoder.com/questionTerminal/d75c232a0405427098a8d1627930bea6
快排也是可以的，多几个指针保存下哨兵位的左右子链表，需要注意的是处理当左右子链表为空的情况
时间复杂度O(nlogn)，空间复杂度其实是O(logn)，因为有栈的开销，但是其他解答里都是归并，其实也差不多，只有那个用cut的是满足题意的
ListNode* sort_inner_impl(ListNode* head, ListNode* end){
if(!head || !head->next || head==end || head->next == end)return head;
ListNode* lefthead,*leftend,*righthead,*rightend;
ListNode* p=head;
ListNode* cmp=head;
lefthead=righthead=leftend=rightend=nullptr;
while(p->next != end){
p=p->next;
if(p->val < cmp->val){
if(!lefthead){
lefthead=p;
}else{
leftend->next=p;
}
leftend=p;
}else{
if(!righthead){
righthead=p;
}else{
rightend->next=p;
}
rightend=p;
}
}
if(!lefthead){
lefthead=cmp;
}else{
leftend->next=cmp;
lefthead = sort_inner_impl(lefthead, cmp);
}
if(!righthead){
cmp->next=end;
}else{
rightend->next = end;
righthead = sort_inner_impl(righthead, end);
cmp->next=righthead;
}
return lefthead;
}
ListNode* sortList(ListNode* head) {
// write code here
return sort_inner_impl(head, nullptr);
} 
