题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
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; } };