题目
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：- 链表中节点的数目在范围 [0, 5 * 104] 内
- -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
我的代码（Python）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
void sortListInner(ListNode* prev, ListNode* endNode = nullptr) {
if (!prev || prev == endNode || !prev->next || prev->next == endNode || !prev->next->next || prev->next->next == endNode) return;
int cnt = 0;
for(ListNode* t = prev->next; t && t != endNode; t = t->next) {
cnt++;
}
ListNode* t0 = prev;
ListNode* t1 = prev->next;
for (int i = 0; i < cnt / 2; i++) {
t0 = t1;
t1 = t1->next;
}
ListNode* middle = t1;
t0->next = t1->next;
t1->next = prev->next;
prev->next = t1;
// ListNode* middle = prev->next;
ListNode* tmp0 = middle;
ListNode* tmp1 = middle->next;
ListNode* tmp2 = nullptr;
while (tmp1 && tmp1 != endNode) {
tmp2 = tmp1->next;
if (tmp1->val <= middle->val) {
ListNode* tmp = prev->next;
prev->next = tmp1;
tmp1->next = tmp;
tmp0->next = tmp2;
tmp1 = tmp2;
} else {
tmp0 = tmp1;
tmp1 = tmp2;
}
}
sortListInner(prev, middle);
sortListInner(middle, endNode);
}
public:
ListNode* sortList(ListNode* head) {
ListNode* prev = new ListNode(0, head);
sortListInner(prev);
ListNode* result = prev->next;
delete prev;
return result;
}
};点评
要求O(nlogn)，脑海中第一个想法就是快排，所以用链表来实现快速排序。
不过忽略了递归调用的空间消耗，不是O(1),而是O(logn).
另外我一开始直接取head作为分界点进行前后大小的比较基准，但是这样做在链表本身是倒序排列时，会退化成O(n^2)复杂度，所以在某个case上超时。
因此我还做了一次遍历来找中间结点😂正常来说，快排应该取随机结点才对。
最后勉强通过了测试，但是实在不是个好结果。
官方自底向上的归并排序其实应该算是比较基础的想法了，但是不熟悉，想不到这个方向……
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog