题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
提供两种方法
方法一：归并排序
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;
}
