1)链表快排
p->q之间放着小于pivot的节点,q->next~tail之间放着大于pivot的节点。
class Solution {
public:
ListNode* sortList(ListNode* head) {
quickSort(head,NULL);
return head;
}
void quickSort(ListNode* head,ListNode* tail){
if(head==tail) return;
ListNode *p=head,*q=head->next;
int pivot=head->val;
while(q!=tail){
if(q->val<=pivot){
p=p->next;
swap(p->val,q->val);
}
q=q->next;
}
swap(p->val,head->val);
quickSort(head,p);
quickSort(p->next,q);
}
};
2)链表归并排序
class Solution {
public:
ListNode* sortList(ListNode* head) {
return mergeList(head);
}
ListNode* mergeList(ListNode* head){
if(!head || !head->next) return head;
ListNode *slow=head,*fast=head,*pre=head;
while(fast && fast->next){
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
pre->next=NULL;
ListNode* l=mergeList(head);
ListNode* r=mergeList(slow);
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;
}else{
r->next=merge(l,r->next);
return r;
}
}
};