题解 | #单链表的排序#

ListNode* sortInList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *slow=head,*qulick=head->next;
        while(qulick && qulick->next){
            slow=slow->next;
            qulick=qulick->next->next;
        }
        ListNode * r_head=slow->next;
        slow->next=NULL;
        ListNode *l=sortInList(head);
        ListNode *r=sortInList(r_head);
        return merge(l,r);
    }
    ListNode* merge(ListNode *l, ListNode* r){
        if(!l) return r;
        if(!r) return l;
        if(l->val<r->val){
            l->next=merge(l->next,r);
            return l;
        }
        r->next=merge(l,r->next);
        return r;
    }

ListNode* sortInList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *left=new ListNode(0),*mid=new ListNode(0),*right=new ListNode(0),*p=head,*tmp;
        int pivot=head->val;
        while(p){
            tmp=p->next;
            if(p->val<pivot){
                p->next=left->next;
                left->next=p;
            }else if(p->val==pivot){
                p->next=mid->next;
                mid->next=p;
            }else{
                p->next=right->next;
                right->next=p;
            }
            p=tmp;
        }
        left->next=sortInList(left->next);
        right->next=sortInList(right->next);
        getTail(left)->next=mid->next;
        getTail(mid->next)->next=right->next;
        return left->next;
    }
    
    ListNode* getTail(ListNode* p){
        while(p->next){
            p=p->next;
        }
        return p;
    }