题解 | #单链表的排序#

利用优先队列，也就是一个小根堆进行存储，再一次创建出一个单链表即可，也不失为一种方法。

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    typedef struct ListNode* Node;
    ListNode* sortInList(ListNode* head) {
        priority_queue<int,vector<int>,greater<int>> q;
        Node cur=head;
        while(cur)
        {
            q.push(cur->val);
            cur=cur->next;
        }
        Node virnode=new ListNode(-1);
        Node root=virnode;
        while(q.size())
        {
            root->next=new ListNode(q.top());
            q.pop();
            root=root->next;
        }
        return virnode->next;
    }
};