巧用优先队列与分治法：高效合并 K 个升序链表

在算法的世界里，解决问题的方式方法多种多样，如何选择适合的算法尤为关键。今天，我们将聚焦一个经典问题——合并 K 个升序链表。作为算法领域的资深大牛和自媒体创作者，笔名Echo_Wish，我将从优先队列和分治法两种不同的视角，为大家详细解析这一问题的解决方案。

问题描述

合并 K 个升序链表，即将 K 个已排序的链表合并成一个新的升序链表。这一问题不仅在面试中常见，在实际工程中也有广泛的应用，如合并日志文件、合并排序结果等。

方法一：优先队列

优先队列（Priority Queue）是一种能高效实现插入和删除操作的数据结构。我们可以利用优先队列解决合并 K 个升序链表问题，其核心思想是将每个链表的头节点加入优先队列，然后反复取出队列中的最小节点，接着将其后继节点加入队列，直到队列为空。

import heapqclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeKLists(lists):# 创建一个优先队列heap = []# 将每个链表的头节点加入优先队列for l in lists:if l:heapq.heappush(heap, (l.val, l))dummy = ListNode()current = dummywhile heap:# 取出队列中最小的节点value, node = heapq.heappop(heap)current.next = nodecurrent = current.nextif node.next:heapq.heappush(heap, (node.next.val, node.next))return dummy.next# 示例链表
l1 = ListNode(1, ListNode(4, ListNode(5)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
l3 = ListNode(2, ListNode(6))# 合并链表
merged_list = mergeKLists([l1, l2, l3])
# 输出合并后的链表
while merged_list:print(merged_list.val, end=" -> ")merged_list = merged_list.next
print("None")

在上述代码中，我们首先创建一个优先队列，并将每个链表的头节点加入队列。然后我们通过循环，不断从队列中取出最小节点，并将其后继节点加入队列，直至队列为空。最终，我们得到一个合并后的升序链表。

方法二：分治法

分治法（Divide and Conquer）的核心思想是将问题分解为若干个子问题，分别解决，然后合并子问题的结果。这种方法在合并 K 个升序链表问题中同样适用。

def mergeTwoLists(l1, l2):dummy = ListNode()current = dummywhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextcurrent.next = l1 if l1 else l2return dummy.nextdef mergeKListsDivideAndConquer(lists):if not lists:return Noneif len(lists) == 1:return lists[0]mid = len(lists) // 2left = mergeKListsDivideAndConquer(lists[:mid])right = mergeKListsDivideAndConquer(lists[mid:])return mergeTwoLists(left, right)# 示例链表
l1 = ListNode(1, ListNode(4, ListNode(5)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
l3 = ListNode(2, ListNode(6))# 合并链表
merged_list = mergeKListsDivideAndConquer([l1, l2, l3])
# 输出合并后的链表
while merged_list:print(merged_list.val, end=" -> ")merged_list = merged_list.next
print("None")