Java实现K个排序链表的高效合并：逐一合并、分治法与优先队列详解
在算法和数据结构的学习中，链表是一个非常基础但又极具挑战的数据结构。尤其是当面对合并多个排序链表的问题时，如何在保证效率的前提下实现代码的简洁与高效，往往是算法设计的关键。本文将详细探讨如何使用Java中的优先队列（PriorityQueue）来实现K个排序链表的高效合并，并为常用的解决方案提供示例代码。
1. 问题背景
在这个问题中，我们有K个已经排序的链表，目标是将这些链表合并成一个新的排序链表，并返回合并后的链表头节点。简单的例子如下：
- 链表1：1 -> 4 -> 5
- 链表2：1 -> 3 -> 4
- 链表3：2 -> 6
合并后的链表为：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
这个问题的难点在于如何高效地处理K个链表的合并。以下是三种常用的解决方案。
2. 常用解决方案
- 逐一合并法
逐一合并法的思路是依次合并两个链表，最终得到结果链表。虽然这种方法简单易懂，但其时间复杂度较高，尤其是在链表数量较多的情况下。
示例代码：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeKListsSequentially {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
ListNode mergedList = lists[0];
for (int i = 1; i < lists.length; i++) {
mergedList = mergeTwoLists(mergedList, lists[i]);
}
return mergedList;
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode list3 = new ListNode(2, new ListNode(6));
ListNode[] lists = new ListNode[]{list1, list2, list3};
MergeKListsSequentially solution = new MergeKListsSequentially();
ListNode mergedList = solution.mergeKLists(lists);
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
}
}
解释：
- 通过
mergeTwoLists方法，将两个有序链表合并成一个新的有序链表。 - 在
mergeKLists方法中，通过循环依次合并所有链表。
时间复杂度：
最坏情况下为O(KN)，其中K是链表的数量，N是每个链表的平均长度。
- 分治法
分治法是一种更高效的解决方案，通过递归地将链表分成两部分，分别进行合并，最终得到完整的合并链表。
示例代码：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeKListsDivideAndConquer {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public ListNode mergeKLists(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode left = mergeKLists(lists, start, mid);
ListNode right = mergeKLists(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return mergeKLists(lists, 0, lists.length - 1);
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode list3 = new ListNode(2, new ListNode(6));
ListNode[] lists = new ListNode[]{list1, list2, list3};
MergeKListsDivideAndConquer solution = new MergeKListsDivideAndConquer();
ListNode mergedList = solution.mergeKLists(lists);
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
}
}
解释：
mergeKLists方法通过分治的方式递归地将链表两两合并，最终得到合并的结果链表。
时间复杂度：
时间复杂度为O(N log K)，其中N是所有节点的总数，K是链表的数量。
- 优先队列法
使用优先队列可以更加高效地解决问题。优先队列可以自动维护一个有序的队列，确保每次取出最小的节点，进行合并。
示例代码：
import java.util.PriorityQueue;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeKListsUsingPriorityQueue {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
// 将每个链表的头节点加入优先队列
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
// 创建虚拟头节点
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
// 逐步处理优先队列中的节点
while (!queue.isEmpty()) {
ListNode minNode = queue.poll();
tail.next = minNode;
tail = tail.next;
// 如果最小节点的下一个节点不为空，继续加入优先队列
if (minNode.next != null) {
queue.add(minNode.next);
}
}
// 防止链表成环，尾节点指向null
tail.next = null;
return dummy.next;
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode list3 = new ListNode(2, new ListNode(6));
ListNode[] lists = new ListNode[]{list1, list2, list3};
MergeKListsUsingPriorityQueue solution = new MergeKListsUsingPriorityQueue();
ListNode mergedList = solution.mergeKLists(lists);
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
}
}
解释：
mergeKLists方法使用优先队列存储每个链表的头节点，并逐步处理优先队列中的最小节点，确保合并后的链表依然有序。
时间复杂度：
时间复杂度为O(N log K)，其中N是所有节点的总数，K是链表的数量。
4. 优化
将每个链表的头节点插入优先队列，并通过逐步处理队列中的最小节点来维护链表的顺序。每次从队列中取出一个节点后，我们将该节点的下一个节点（如果存在）加入队列。这样可以减少优先队列的操作次数，从而提高效率。
示例代码：
import java.util.PriorityQueue;
class MergeKSortedListsOptimized {
public ListNode mergeKLists1(ListNode[] lists) {
// 创建一个最小堆优先队列，根据节点的值进行排序
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
// 遍历所有链表
for (ListNode list : lists) {
// 如果链表不为空
if (list != null) {
// 将链表头节点加入优先队列
queue.add(list);
}
}
// 创建一个虚拟头节点
ListNode dummy = new ListNode(0);
// 尾节点指向虚拟头节点
ListNode tail = dummy;
// 当优先队列不为空时
while (!queue.isEmpty()) {
// 从优先队列中取出最小的节点
ListNode minNode = queue.poll();
// 将最小节点连接到当前链表的末尾
tail.next = minNode;
// 更新尾节点为当前最小节点
tail = tail.next;
// 如果最小节点还有下一个节点
if (minNode.next != null) {
// 将最小节点的下一个节点加入优先队列
queue.add(minNode.next);
}
}
// 将尾节点的next指针置为null，表示链表结束
tail.next = null;
// 返回合并后的链表的头节点（虚拟头节点的下一个节点）
return dummy.next;
}
}
解释：
该实现与前一个方法类似，但不同的是我们只将链表的头节点加入优先队列，然后逐个处理节点。在处理每个节点时，如果它有下一个节点，我们将下一个节点加入队列。这样做可以有效减少优先队列的操作次数，提高算法效率。
时间复杂度：
时间复杂度为 O(N * log(K))，其中 K 是链表的数量，N 是所有链表中节点的总数。
4. 总结
通过以上三种常用的解决方案，我们可以清楚地看到，不同的方法在时间复杂度和实现复杂度上的权衡。对于链表数量较少的情况，逐一合并法可能更简单易行；而在链表数量较多时，分治法和优先队列法则可以更高效地解决问题。在实际开发中，优先队列法常常是首选，因为它在效率和实现上都表现得十分优秀。
![[C++] C++11详解 (一)](https://i-blog.csdnimg.cn/direct/162083f688e54458963640439ee57f22.png)
