题解 | #单链表的排序#

这道题就是简单的链表排序题，因为看到时间复杂度是O(nlogN),而数组排序最快也差不多O(nlogN),而且没有规定空间复杂度，所以这里直接遍历一次将所有指向节点的指针放入vector,根据val大小快排，然后根据大小重新将指针赋值。

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
bool cmp1(ListNode* a,ListNode*b)
{
    return a->val<b->val;
}
class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* sortInList(ListNode* head) {
        // write code here
        
        
        ListNode* st = head;
        vector<ListNode*> aux;
        while(st!=NULL)
        {
            aux.push_back(st);
            st = st->next;
        }
        sort(aux.begin(),aux.end(),cmp1);
        ListNode* head1 = NULL;
        for(int i =0;i<aux.size();i++)
        {
            aux[i]->next = NULL;
            if(i==0)
                head1 = aux[i];
            else
                aux[i-1]->next = aux[i];
        }
        return head1;
    }
};