题解 | #单链表的排序#

//时间复杂度O(nlog(n)),可以用快排，但是快排最坏也是O(n*n),可以用数组，或者动态数组(这里我都试了一下，区别不大，数据多了数组还是会好一点吧，动态数组扩容是非常耗时间的)存贮链表的节点，然后根据节点的val值排序

#include <any>
#include <random>
#include <vector>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    void quick_sort(ListNode* array[],int begin,int end)
    {
        if(begin >= end) return;
        ListNode* mid = array[(begin + end) >> 1];
        int left = begin - 1;
        int right = end + 1;
        while(left < right)
        {
            do left++;  while(array[left]->val < mid->val);
            do right--; while(array[right]->val > mid->val);
            if(left < right) swap(array[left],array[right]);
        }
        quick_sort(array,begin,right);
        quick_sort(array,right + 1,end);
    }
    ListNode* sortInList(ListNode* head) 
    {
        if(!head||!head->next) return head;
        ListNode *pNode = head;
        int size = 0;
        while(pNode)
        {
            size++;
            pNode = pNode->next;
        }
        pNode = head;
        int i = 0;
        ListNode* array[size]; 
        while(pNode)
        {
            array[i++] = pNode;
            pNode = pNode->next;
        }
        quick_sort(array,0,size-1);
        head = array[0]; 
        for(int i = 0;i < (size-1); i++)
        {
            array[i]->next = array[i+1];
        }
        array[size-1]->next = nullptr;
        return head;
    }
};