AcWing 1451. 单链表快速排序
原题链接
简单
作者:
我要出去乱说
,
2021-02-01 16:57:40
,
所有人可见
,
阅读 507
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* get_tail(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); //定义三个链表
auto ltail = left, mtail = mid, rtail = right; //定义三个链表结尾
int val = head->val;
for (auto p = head; p; p = p->next) { //遍历当前单链表
if (p->val < val) ltail = ltail->next = p; //尾结点赋值并向后移动一位,一气呵成
else if (p->val == val) mtail = mtail->next = p;
else rtail = rtail->next = p;
}
ltail->next = mtail->next = rtail->next = NULL;
left->next = quickSortList(left->next);
right->next = quickSortList(right->next);
//拼接三个链表
get_tail(left)->next = mid->next;
get_tail(left)->next = right->next; //中间不一定存在,且此时左边和中间已经合并
auto p = left->next;
delete left;
delete mid;
delete right;
return p; //释放空间,严谨
}
};