LeetCode 148. 排序链表
原题链接
中等
作者:
linux_2019
,
2019-09-23 12:40:23
,
所有人可见
,
阅读 648
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * partition(ListNode * l,ListNode * r)
{
ListNode * dummy=new ListNode(-1);
ListNode * i=dummy;
i->next=l;
ListNode*t=r;
for(ListNode *j=l;j!=r;j=j->next)
{
if(j->val < t->val)
{
i=i->next;
swap(i->val,j->val);
}
}
// if(i!=l)
swap(i->next->val,r->val);
if(i==dummy )
return i->next;
else return i;
}
void quick_sort(ListNode * l,ListNode * r )
{
if(l==r)
return ;
ListNode *mid=partition(l,r);
quick_sort(l,mid);
quick_sort(mid->next,r);
}
ListNode* sortList(ListNode* head) {
if(!head) return NULL;
ListNode * r=head;
while(r->next) r=r->next;
quick_sort(head,r);
return head;
}
};