题解 | #单链表的排序#

//学会使用 priority_queue,默认大顶堆，pop后从大到小排序。
class Solution {
public:
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        priority_queue<pair<int,ListNode*>> nQueue;
        ListNode* nhead = head;
        ListNode* nList = new ListNode(0);
        ListNode* listHead;
        while (nhead)
        {
            nQueue.push(pair<int, ListNode*>(nhead->val, nhead ) );
            nhead = nhead->next;
        }
        while (!nQueue.empty())
        {
            listHead = nList->next;
            nQueue.top().second->next = listHead;
            nList->next = nQueue.top().second;
            nQueue.pop();
            
        }
        //nList->next = nullptr;
        return nList->next;
    }
};