当前位置：首页 > article >正文

LeetCode-合并 K 个升序链表（023）

article 2025/1/8 7:21:25

一.题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

二.示例

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

三.提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

四.解法:

方法一：优先队列（小根堆）

我们可以创建一个小根堆来 pq 维护所有链表的头节点，每次从小根堆中取出值最小的节点，添加到结果链表的末尾，然后将该节点的下一个节点加入堆中，重复上述步骤直到堆为空。

时间复杂度 O(n×log⁡k)，空间复杂度 O(k)。其中 n 是所有链表节点数目的总和，而 k 是题目给定的链表数目。

五.代码

Java代码

/**
 * Definition for singly-linked list.
 * 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) {
        // 创建一个优先队列（最小堆），用于存储链表节点
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // 将每个链表的头节点加入优先队列
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head);
            }
        }
        
        // 创建一个哑节点，作为合并链表的头节点
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        
        // 当优先队列不为空时，处理节点
        while (!pq.isEmpty()) {
            // 取出优先队列中最小的节点
            ListNode node = pq.poll();
            
            // 如果该节点有下一个节点，将下一个节点加入优先队列
            if (node.next != null) {
                pq.offer(node.next);
            }
            
            // 将当前节点连接到合并链表中
            cur.next = node;
            cur = cur.next;
        }
        
        // 返回合并后的链表
        return dummy.next;
    }
}

注释说明
    ·优先队列：使用 PriorityQueue 来存储链表节点，按节点值排序，以便每次取出最小的节点。
    ·初始化队列：遍历输入的链表数组，将每个链表的头节点加入优先队列。
    ·哑节点：dummy 节点用于简化链表操作，最终返回合并链表的头节点。
    ·合并过程：从优先队列中取出最小节点，将其连接到合并链表中。
        ·如果取出的节点有后续节点，将后续节点加入优先队列。
    ·返回结果：返回合并后的链表，跳过哑节点。