题目描述:

给定一个单链表，请使用快速排序算法对其排序。

要求：期望平均时间复杂度为 O(nlogn)O(nlogn)，期望额外空间复杂度为 O(logn)O(logn)。

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

数据范围

链表中的所有数大小均在 intint 范围内，链表长度在 [0,10000][0,10000]。

输入样例：

[5, 3, 2]

输出样例：

[2, 3, 5]

前言：

一般工程当中，val可能有很多个属性，交换其属性可能会很慢，故交换指针。

算法思路：

• 开三个子链表去分别存储

小于头第一个点的值（[HTML_REMOVED]left）

等于第一个点的值（=val->mid）

大于第一个点的值（>val->right）

left、mid、right分别为三个集合（子链表）

遍历整个链表，对总链表进行划分，分别归到合适的子链表中

归类结束后，一定将子链表的结尾置为空，随后进行递归排序

递归排序后，对链表进行拼接，由于中间一段的子链表不一定存在，所以从头开始找，即从最左边开始找

拼接完后 记得释放空间

AC代码:

/**
 * 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;//如果头节点不存在 或者 只有头节点一个节点

        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=mtail->next=rtail->next=nullptr;
        //递归进行排序
        left->next=quickSortList(left->next);
        right->next=quickSortList(right->next);

        //拼接三个链表
        get_tail(left)->next=mid->next;
        //中间这一段不一定存在 所以从头开始找，即从最左边开始找
        get_tail(left)->next=right->next;

        auto p=left->next;
        delete left;
        delete mid;
        delete right;

        return p;

    }
};