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

本来的方案：在方法内部，首先进行了一些边界检查，如果头结点为null，则直接返回null。

然后，创建了一个优先队列PriorityQueue，并使用自定义比较器（Comparator）来构造小根堆。该比较器的compare方法根据节点的值进行比较，以确保小的值在队列的前面。

接下来，通过循环遍历链表，将每个节点都添加到优先队列中。

然后，创建了一个虚拟头结点dummy和一个指针cur，用于构建排序后的链表。

在循环结束后，开始从优先队列中将节点取出，并按顺序连接到排序链表的末尾。最后，返回排序后的链表的头结点。

public class Solution {

    public ListNode sortList (ListNode head) {
        if(head==null) return head;
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
            public int compare(ListNode p1,ListNode p2){
                return p1.val-p2.val; //小根堆
            }
        });
        while(head!=null) {
            pq.add(head);
            head=head.next;
        }
        ListNode dummy =new ListNode(-1),cur=dummy;
        while(!pq.isEmpty()){
            cur.next=pq.poll();
            cur=cur.next;
        }

        return dummy.next;
    }
}

结果内存超限了，只通过 4/5个用例。于是

把存节点改为了存值，顺利通过啦

public class Solution {

    public ListNode sortList (ListNode head) {
        if (head == null) return head;

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while (head != null) {
            pq.add(head.val);
            head = head.next;
        }
        ListNode dummy = new ListNode(-1), cur = dummy;
        while (!pq.isEmpty()) {
            ListNode tmp = new ListNode(pq.poll());
            cur.next = tmp;
            cur = cur.next;
        }

        return dummy.next;
    }
}