1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public static ListNode mergeKLists(ArrayList<ListNode> arr) {
        // 初始化小顶堆：按节点值升序排序，每次取出当前最小的节点
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((a, b) -> (a.val - b.val));
        
        // 将非空的头节点加入小顶堆
        for (int i = 0; i < arr.size(); i++) { 
            ListNode head = arr.get(i);
            if (head != null) { // 跳过空链表，避免堆中加入null
                pq.add(head);
            }
        }

        // 哨兵节点：简化链表拼接逻辑，无需处理头节点为空的情况
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy; // 合并链表的尾节点指针，初始指向哨兵节点

        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll(); // 取出当前所有链表的最小节点
            curr.next = minNode;          // 拼接到合并链表尾部
            curr = curr.next;             // 尾节点指针后移

            // 若当前最小节点的下一个节点非空，加入堆中继续参与排序
            if (minNode.next != null) {
                pq.add(minNode.next);
            }
        }

        // 哨兵节点的next即为合并后的真实头节点
        return dummy.next;
    }