acwing1451. 单链表快速排序

class Solution {
public:
    ListNode* gettail(ListNode* head){
        while(head->next)head=head->next;
        return head;
    }
    ListNode* quickSortList(ListNode* head) {
        if(!head||!head->next)return head;
        auto left=new ListNode(-1),mid=new ListNode(-1),right=new ListNode(-1);
        int val=head->val;
        auto ltail=left,mtail=mid,rtail=right;
        for(auto p=head;p;p=p->next){
            if(p->val<val)ltail=ltail->next=p;
            else if(p->val>val)rtail=rtail->next=p;
            else mtail=mtail->next=p;
        }
        ltail->next=rtail->next=mtail->next=NULL;
        left->next=quickSortList(left->next);
        right->next=quickSortList(right->next);
        gettail(left)->next=mid->next;
        gettail(left)->next=right->next;
        auto p=left->next;
        delete left;
        delete right;
        delete mid;
        return p;
    }
    
};