题解 | #牛群的身高排序# 排序应用题

知识点

快速排序 计数排序 链表

思路分析

求的是整个链表的按值排序后的结果，可以把所有的值取出来进行排序后再重新连接为新的链表。在实现上可以建立虚拟头结点简化代码逻辑。

排序可以选择快速排序或者 计数排序

时间复杂度

遍历链表的复杂度为

排序的复杂度为或者

瓶颈在排序上

AC code (C++)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortList(ListNode* head) {
        vector<vector<ListNode*>> a(10010);
        auto p = head;
        while (p) {
            a[p->val].push_back(p);
            p = p->next;
        }
        auto dummy = new ListNode(-1);
        p = dummy;
        for (int i = 0; i <= 10000; i ++) {
            for (auto x : a[i]) {
                p->next = x;
                p = p->next;
            }
        }
        p->next = nullptr;
        return dummy->next;
    }
};