leetcode23-合并K个升序链表-白红宇

leetcode23-合并K个升序链表

阅读量：791 次

发布时间：2023-01-31

本文共 1610 字，大约阅读时间需要 5 分钟。

为了合并所有给定的按升序排列的链表数组，使用优先队列是高效且简便的方法。优先队列始终提取出当前最小的节点，确保生成的链表是升序排列的。以下是具体步骤：

初始化优先队列：将所有链表中的节点依次加入优先队列，队列按节点的值从小到大排序。

创建虚拟头结点：用来构造最终的升序链表。

遍历优先队列：每次取出队列中的最小节点，将其连接到结果链表的末尾。

处理结果链表结尾：确保没有游标指向未处理节点。

这种方法的时间复杂度为O(n log n)，其中n是所有链表节点的总数，适用于大范围数据。

代码实现：

import java.util.PriorityQueue;import java.util.Comparator;class Solution {    public ListNode mergeKLists(ListNode[] lists) {        if (lists == null || lists.length == 0) {            return null;        }                // 比较器用于根据节点的值排序        Comparator
   
     comparator = new Comparator
    
     () {            @Override            public int compare(ListNode o1, ListNode o2) {                return Integer.compare(o1.val, o2.val);            }        };                PriorityQueue
     
       pqueue = new PriorityQueue<>(comparator);                // 将所有列表中的节点加入优先级队列        for (ListNode list : lists) {            ListNode current = list;            while (current != null) {                pqueue.offer(current);                current = current.next;            }        }                // 虚拟头节点作为结果链表的起点        ListNode head = new ListNode(0);        ListNode result = head;                // 依次将最小节点提取出来，连接到结果链表中        while (!pqueue.isEmpty()) {            ListNode minNode = pqueue.poll();            result.next = minNode;            result = minNode;        }                // 定义返回的起始节点        return head.next;    }}

代码解释：