归并排序

择期另更

排序将链表值存放到数组排好序再放回到链表

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        ListNode* temp = head;
        vector<int> x;
        
        while(temp){
            x.push_back(temp->val);
            temp = temp->next;
        }
        int i=x.size();
        //冒泡循环复杂度过高
        // for(int j = 0;j<i;j++){
        //     for(int k=j+1;k<i;k++){
        //         if(x[j]>x[k]){
        //             int top = x[j];
        //             x[j]=x[k];
        //             x[k]=top;
        //         }
        //     }
        // }
      
      	//快排
        sort(x.begin(),x.end());
        temp = head;
        i = 0;
        while(temp){
            temp->val = x[i++];
            temp = temp->next;
        }
        return head;
    }
};