题解 | #单链表的排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here

        // 借助小根堆实现 - 注意别忘了自定义类的排序需要写比较器

        // 算法时间复杂度O(NlogN)，额外空间复杂度O(N)

        // 1.先排除null和单值
        if(head == null || head.next == null) {
            // 无需排序
            return head;
        }

        // 2.遍历链表，依次将结点入堆
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        ListNode cur = head;
        while (cur != null) {
            // 堆的插入 - offer
            minHeap.offer(cur);
            System.out.println("结点入堆：" + cur.val);
            cur = cur.next;
        }

        // 3.依次出堆，尾插法建立result链表
        ListNode result = null;
        ListNode tail = result;
        while(!minHeap.isEmpty()) {
            // 依次弹出堆中所有结点，使用尾插法将它们连接起来
            // 堆的弹出 - poll
            ListNode rootNode = minHeap.poll();
            System.out.println("结点出堆：" + rootNode.val);
            rootNode.next = null;
            if (tail == null) {
                // 尾插第一个元素
                result = rootNode;
                tail = result;
            } else {
                tail.next = rootNode;
                tail = rootNode;
            }
        }
        // 4.返回结果链表的头结点result
        return result;
    }
}