【题目来源】
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/