合并K个排序链表：PriorityQueue比较器必要性的疑问

我在实现合并K个排序链表时遇到了疑问，相关题目是LeetCode上的合并K个排序链表。

ListNode定义 #

public class ListNode {
  
  int val;
  ListNode next;

  ListNode() {
  }

  ListNode(int val) {
    this.val = val;
  }

  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

我的实现代码 #

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists==null || lists.length==0) return null;
         PriorityQueue<ListNode> pq= new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);
         ListNode head=new ListNode(-1);
        ListNode tail=head;
        for(ListNode node:lists){
          if(node!=null)
           pq.add(node);
        }

        
        while(!pq.isEmpty()){
            tail.next=pq.poll();
            tail=tail.next;

            if(tail.next!=null){
                pq.add(tail.next);
            }
        }
        return head.next;
    }
}

疑问点 #

我对这行代码存在疑问：PriorityQueue<ListNode> pq= new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);

• 默认PriorityQueue不是会优先取出最小元素吗？为什么不能直接添加节点之后再取出？
• 插入Integer类型元素时为什么不需要比较器？

问题解答 #

为什么ListNode必须指定比较器？ #

Java的PriorityQueue默认是小顶堆，但它的默认排序依赖元素的自然排序——要求元素必须实现Comparable接口，重写compareTo方法，明确两个元素的比较规则。

Integer类本身就实现了Comparable<Integer>接口，自带数值大小的比较逻辑，所以直接放入PriorityQueue时，队列知道怎么排序，不用额外指定比较器。

但你自定义的ListNode类没有实现Comparable接口，JVM完全不知道该怎么比较两个ListNode的大小：是比val字段？还是比next的内存地址？如果不指定比较器，往队列添加元素时会直接抛出ClassCastException，因为队列无法将ListNode转换为Comparable类型执行比较。

为什么不能直接添加节点再取出？ #

如果不指定比较器，连添加节点这一步都无法完成，更别说取出元素了。你可以试试去掉比较器运行代码，肯定会报错——因为PriorityQueue没有排序规则，根本无法处理ListNode元素。

你写的(a,b)-> a.val-b.val这个Lambda表达式，就是给队列明确了排序逻辑：比较两个ListNode的val值，val小的排在前面。这样队列每次poll()出来的都是当前所有节点中val最小的，正好满足合并K个有序链表的需求——每次取最小节点接在结果链表上，再把该节点的下一个节点放入队列继续参与排序。

内容的提问来源于stack exchange，提问作者Naina Mathur