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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>

// struct cmp{
//     bool operator ()(ListNode* l1,ListNode* l2)
//     {
//         return l1->val < l2->val;
//     }
// };

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortList(ListNode* head) {
        // write code here
        // 方法一：利用vector + sort排序 + 创建新链表

        // 方法二：利用优先队列priority_queue<>;
        
        // 排序方式，值大的在栈低；
        auto cmp = [](ListNode* l1,ListNode* l2){return l1->val > l2->val;};
        // 定义：priority_queue<Type, Container, Functional>
        // Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

        // 自定义比较方法可以利用结构体，也可以用匿名函数（lambda表达式）
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> p_q(cmp);
        
        ListNode* t = head;
        while(t)
        {
            ListNode* t_2 = t->next;
            t->next = nullptr;
            
            p_q.push(t);

            t = t_2;
        }

        // 创建链表
        ListNode* ans = new ListNode(-1);
        t = ans;
        int size = p_q.size();

        for(int i=0; i<size; ++i)
        {
            t->next = p_q.top();
            p_q.pop();
            t = t->next;
        }

        return ans->next;
    }   
};