题解 | #单链表的排序#

1. 解题思路

时间复杂度要求O(nlogn)，冒泡排序时间为O(n^2)大概率会超时，所以想到快排。因为链表结构不能随机访问，所以建立vector先将链表数据保存到vector中，将对链表排序转换为对数组排序。有两种方案：

1.vector保存每个结点的值对值排序后将结果按顺序为链表每个结点赋值。这时问题变成了简单的对数组元素排序。

2.vector保存每个结点的指针以上方案对结点的值进行了修改，如果不想修改结点值，就要比较结点值为结点指针排序。以下代码为该方案的实现。

本来自己写了快排函数quick_sort，但是会超时。最终使用了模板库提供的sort函数。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
  	//自己写的对结点指针的快排算法，会超时，转而使用sort函数
  /**
    void quick_sort(vector<ListNode*> &plist,int start,int end){
        if (start>=end)
            return;
        int pivot = plist[start]->val;
        ListNode* pivot_pr = plist[start];
        int front = start;
        int rear = end;
        while(front<rear){
            for(;rear>front && plist[rear]->val>=pivot;rear--);
            if(rear>front){
                plist[front] = plist[rear];
                front++;
            }
            for(;rear>front && plist[front]->val<=pivot;front++);
            if(rear>front){
                plist[rear] = plist[front];
                rear--;
            }           
        }
        plist[front] = pivot_pr;
        quick_sort(plist,start,front-1);
        quick_sort(plist,front+1,end);    
    }
	*/
  
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        vector<ListNode*> plist;
	  	//将每个结点的指针保存到vector中
        while(head){
            plist.push_back(head);
            head = head->next;
        }   
        // quick_sort(plist,0,plist.size()-1); //超时不用
	  	
	  //定义排序规则，使用结点的值去比较
        auto cmp = [](ListNode* a, ListNode* b) -> bool {
            return a->val < b->val;
        }; 
        sort(plist.begin(),plist.end(),cmp);
	  	
	  //将排好序的链表结点连接成完整的链表
        ListNode* res = new ListNode(0);
        ListNode* tmp = res;
        for(int i=0;i<plist.size();++i){
            tmp->next = plist[i];
            tmp = plist[i];
        }
        tmp->next = NULL;
        return res->next;
    }
};