题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
     struct cmp{
      bool operator()(ListNode* node1,ListNode* node2){
          return node1->val>node2->val;
      }
     };
    ListNode* sortInList(ListNode* head) {
       priority_queue<ListNode*,vector<ListNode*>,cmp>pq;
       while(head){
        pq.push(head);
        head=head->next;
       }
       ListNode* list=new ListNode(-1);
       ListNode* pre=list;
       while(!pq.empty()){
        list->next=pq.top();
        list=list->next;
        list->next = nullptr;//防止形成循环队列
        pq.pop();
        cout<<1<<endl;
       }
     return pre->next;
    }
};

使用优先级队列要注意将当前节点的下一个节点的地址信息置空，防止形成循环链表