单链表快速排序

思路：

和普通快排一样，递归实现遍历。递归的每一层都遍历一遍当前的链表，将链表按照节点值分成三部分：等于枢轴值、小于枢轴值和大于枢轴值。递归排序后，将三段链表进行拼接。

时空复杂度：

平均时间复杂度为 O(nlogn)，额外空间复杂度为 O(logn)。

代码：

class Solution {
public:
    //返回指向当前链表的尾节点指针
    ListNode* get(ListNode* head)
    {
        while(head->next) head = head->next;
        return head;
    }
    ListNode* quickSortList(ListNode* head) {
        if(!head || !head->next) return head;//头结点为空或当前只有头结点
        ListNode *s = new ListNode(-1), *e = new ListNode(-1), *l = new ListNode(-1);
        ListNode *st = s, *et = e, *lt = l;//尾指针，一直指向最后一个节点
        int v = head->val;//枢轴值
        for(auto iter = head; iter != nullptr; iter = iter->next)
        {
            if(iter->val < v) st = st->next = iter;//当前iter接到当前st后，再将st指向新末尾
            else if(iter->val == v) et = et->next = iter;
            else lt = lt->next = iter;
        }
        st->next = et->next = lt->next = nullptr;//因为原节点指针是指向下一节点的，被取出后最后一个节点应指向空
        s->next = quickSortList(s->next);
        l->next = quickSortList(l->next);
        get(s)->next = e->next;
        get(s)->next = l->next;//防止某一个为空
        auto res = s->next;
        delete s, e, l;
        return res;
    }
};