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

LeetCode 23：合并 K 个升序链表

news 2025/7/25 11:19:06

LeetCode 23：合并 K 个升序链表

在这里插入图片描述

问题本质：多有序链表的归并

给定 K 个升序链表，需合并为一个全局升序链表，返回其头节点。核心是高效处理多链表的有序合并，避免暴力法的高复杂度。

核心思路：两种高效解法

1. 优先队列（最小堆）

核心逻辑：维护当前所有链表头节点的最小值，每次取最小节点加入结果，再将该节点的下一个节点（若存在）加入堆，循环至所有节点处理完毕。
优势：利用堆的排序特性，保证每次取最小值的时间为 O(logK)，整体高效。

2. 分治合并

核心逻辑：类似归并排序，将 K 个链表递归拆分为两两一组，合并后再递归合并结果，最终得到全局有序链表。
优势：递归结构清晰，空间复杂度更优（递归栈深度为 O(logK)）。

方法一：优先队列（最小堆）详解

步骤 1：处理边界情况

若 lists 为空或所有链表为空，直接返回 null。

步骤 2：初始化优先队列

使用 PriorityQueue 实现最小堆，比较器按节点值从小到大排序。
遍历 lists，将非空链表的头节点加入堆（过滤空链表，避免空指针）。

步骤 3：构建结果链表

创建虚拟头节点（dummy），简化链表拼接（无需处理头节点为空的边界）。
循环处理堆：
1. 取出堆顶元素（当前最小节点），接入结果链表。
2. 若该节点有下一个节点，将其加入堆（维持堆的动态更新）。

步骤 4：返回结果

虚拟头节点的 next 即为合并后链表的头节点。

方法二：分治合并详解

步骤 1：递归终止条件

若链表数组为空，返回 null。
若只剩一个链表，直接返回该链表（递归基例）。

步骤 2：递归拆分

将链表数组分为左右两半，递归合并左右部分，得到两个局部合并后的链表 l1 和 l2。

步骤 3：合并两个有序链表

实现辅助函数 mergeTwoLists，用双指针法合并两个有序链表：
- 比较两链表当前节点值，将较小值接入结果链表，指针后移。
- 处理剩余未遍历的节点（直接拼接）。

步骤 4：递归合并结果

合并 l1 和 l2，返回最终结果。

完整代码实现

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

/*** 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) {// 边界处理：空输入if (lists == null || lists.length == 0) return null;// 初始化最小堆，按节点值排序PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);// 将非空链表的头节点加入堆for (ListNode head : lists) {if (head != null) {minHeap.offer(head);}}// 虚拟头节点，简化拼接ListNode dummy = new ListNode(-1);ListNode curr = dummy;// 处理堆中的节点while (!minHeap.isEmpty()) {ListNode minNode = minHeap.poll(); // 取出当前最小节点curr.next = minNode;              // 接入结果链表curr = curr.next;                 // 指针后移// 将下一个节点加入堆（若存在）if (minNode.next != null) {minHeap.offer(minNode.next);}}return dummy.next;}
}

方法二：分治合并

/*** 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) {if (lists == null || lists.length == 0) return null;return merge(lists, 0, lists.length - 1);}// 递归合并区间 [left, right] 的链表private ListNode merge(ListNode[] lists, int left, int right) {if (left == right) {return lists[left]; // 单个链表，直接返回}int mid = left + (right - left) / 2; // 避免整数溢出ListNode l1 = merge(lists, left, mid);ListNode l2 = merge(lists, mid + 1, right);return mergeTwoLists(l1, l2);}// 合并两个有序链表（双指针法）private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1);ListNode curr = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}// 拼接剩余节点（其中一个链表已遍历完）curr.next = (l1 != null) ? l1 : l2;return dummy.next;}
}