题解 | 单链表的排序

import java.util.*; 
import java.util.PriorityQueue;

/*
 * 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) {
        if(head == null || head.next == null) {
            return head;
        }
	  	// 申明一个优先级队列，并传入一个比较器，比较ListNode中val值的大小
        Queue<ListNode> queue = new PriorityQueue<>((x,y) -> {
            return x.val - y .val;
        });
	  	// 把ListNode中所有的节点放入到优先级队列中
        queue.add(head);
        while(head.next != null) {
            head = head.next;
            queue.add(head);
        }
		// 从优先级队列中poll元素，组装结果
        ListNode result = queue.poll();
        ListNode tempNode = result;
        while(!queue.isEmpty()) {
            tempNode.next = queue.poll();
            tempNode = tempNode.next;
        }
	 	// 把最后一个节点的下一个节点置为null，防止循环
        tempNode.next = null;
        return result;
    }
}