面试题|面试题——单链表快速排序面试题|李明徽的算法

AcWing 1451 单链表快速排序题目给定一个单链表，请使用快速排序算法对其排序
【面试题|面试题——单链表快速排序】要求：期望平均时间复杂度为O(nlogn)，期望额外空间复杂度为O(logn)
思考题：如果只能改变链表结构，不能修改每个节点的val值该如何做呢
数据范围链表中的所有数大小均在int范围内，链表长度在[0, 10000]
输入样例：

[5, 3, 2]

输出样例：

[2, 3, 5]

思路 ? 首先我们要思考快排的思想
? 快排就是选定一个目标值，将比目标值小的都放在左边，比目标值大的都放在右边，然后递归处理左边和右边，最后将三者（还有等于目标值的可能）合并，那在链表中如何实现快排呢
? 很简单，我们要定义三个链表，分别代表left、mid、right，我们设定一个目标值，假设为int val = head->val，通过遍历原链表，我们将比val小的放在left后，将比val大的放在right后，相等的放在mid后，然后递归处理left和right，最后将三者连接即可
? 这里需要注意几个细节，因为三个链表的表头指针我们后面会用到，所以我们需要一个变量来记录每个链表尾节点的指针：ltail、mtail、rtail，通过这三个指针，我们可以实现向链表尾插入数据；在遍历链表结束后，要将三个尾指针指空，否则系统无法判断链表是否结束了，下面是代码
代码

class Solution { public: 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 = rtail->next = mtail->next = NULL; left->next = quickSortList(left->next); right->next = quickSortList(right->next); auto lh = left; while (lh->next) lh = lh->next; lh->next = mid->next; while (lh->next) lh = lh->next; lh->next = right->next; return left->next; } };