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;
}
};