AcWing 1451：单链表快速排序

【题目来源】
https://www.acwing.com/problem/content/1453/

【题目描述】
给定一个单链表，请使用快速排序算法对其排序。
要求：期望平均时间复杂度为 O(nlogn)，期望额外空间复杂度为 O(logn)。
思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

【数据范围】
链表中的所有数大小均在 int 范围内，链表长度在 [0,10000]。
本题数据完全随机生成。

【输入样例】
[5, 3, 2]

【输出样例】
[2, 3, 5]

【算法代码】
下面代码转载自：https://www.acwing.com/solution/content/57352/

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:ListNode* quickSortList(ListNode* head) {if(!head) return head;quickSort(head, NULL);return head;}void quickSort(ListNode* head, ListNode* tail) {if(head!=tail) {int key=head->val;ListNode *p=head, *q=p->next;while(q!=tail) {if(q->val < key) {p=p->next;swap(p->val,q->val);}q=q->next;}if(p!=head){swap(head->val,p->val);}                    quickSort(head,p);quickSort(p->next,tail);}}
};

【参考文献】
https://www.acwing.com/solution/content/57352/