单链表快速排序
作者:
虎头虎脑
,
2022-04-21 21:02:50
,
所有人可见
,
阅读 243
个人版视频笔记 https://www.bilibili.com/video/BV1KS4y1a7xA/
class Solution {
public:
ListNode* quickSortList(ListNode* head) {
if(head == NULL) return head;
quick_sort(head, NULL);
return head;
}
void quick_sort(ListNode *head, ListNode *tail)
{
if(head != tail)
{
int key = head -> val;
auto p = head, q = head->next;
while(q != tail)
{
if(q->val < key)
{
p = p->next;
swap(p->val, q->val);
}
q = q->next;
}
if(head != p)
{
swap(head->val, p->val);
}
quick_sort(head, p);
quick_sort(p->next, tail);
}
}
};