题目： AcWing 1451. 单链表快速排序
给定一个单链表，请使用快速排序算法对其排序。
要求：期望平均时间复杂度为 O(nlogn)，期望额外空间复杂度为 O(logn)。
思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？
数据范围
链表中的所有数大小均在 int 范围内，链表长度在 [0,10000]。
输入样例：
[5, 3, 2]
输出样例：
[2, 3, 5]
题目分析：
快速排序的思路
1.首先找到基准值，链表找第一个就可以了
2.然后将整条链表分段，链表可以分成三段，小于，等于，大于
3.最后递归然后将三段进行拼接即可
注意：
链表题一来先判断是否为空 if(!head||!head->next)return head;
尾结点要置为NULL，不然循环有问题
递归注意结点可能为空，不能随意进行操作，可能会抱错
如果要严谨就释放空间
/**
* 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;
// 声明三个头结点，和三个对应的尾结点
ListNode *left=new ListNode(-1),*mid=new ListNode(-1),*right=new ListNode(-1);
ListNode *ltail=left,*mtail=mid,*rtail=right;
int val=head->val;
// 循环将结点分成三组
while(head)
{
if(head->val>val)rtail=rtail->next=head;
else if(head->val==val)mtail=mtail->next=head;
else ltail=ltail->next=head;
head=head->next;
}
// 要将尾节点置为NULL
ltail->next=rtail->next=mtail->next=NULL;
left->next=quickSortList(left->next);
right->next=quickSortList(right->next);
// 将三段进行拼接
get_tail(left)->next=mid->next;
get_tail(left)->next=right->next;
// 释放空间
ListNode *res=left->next;
delete left;
delete mid;
delete right;
return res;
}
};