Java实现K个排序链表的高效合并：逐一合并、分治法与优先队列详解

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. 常用解决方案

1. 逐一合并法

逐一合并法的思路是依次合并两个链表，最终得到结果链表。虽然这种方法简单易懂，但其时间复杂度较高，尤其是在链表数量较多的情况下。

示例代码：

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是每个链表的平均长度。

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 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是链表的数量。

3. 优先队列法

使用优先队列可以更加高效地解决问题。优先队列可以自动维护一个有序的队列，确保每次取出最小的节点，进行合并。

示例代码：

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);}}// 防止链表成环，尾节点指向nulltail.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. 总结

通过以上三种常用的解决方案，我们可以清楚地看到，不同的方法在时间复杂度和实现复杂度上的权衡。对于链表数量较少的情况，逐一合并法可能更简单易行；而在链表数量较多时，分治法和优先队列法则可以更高效地解决问题。在实际开发中，优先队列法常常是首选，因为它在效率和实现上都表现得十分优秀。