快排也是可以的，多几个指针保存下哨兵位的左右子链表，需要注意的是处理当左右子链表为空的情况
时间复杂度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);
    }