题解 | 单链表的排序

import java.util.*;


public class Solution {

    public ListNode sortInList (ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });
        while (head != null) {
            queue.offer(head);
            head = head.next;
        }

        ListNode start = new ListNode(0);
        ListNode pre = start;
        //OOM
        ListNode tmp = null;
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            //一定要把原先链表断开
            tmp.next = null;
            pre.next = tmp;
            pre = pre.next;
        }
        return start.next;
    }
}