题目描述：K个有序链表的合并难题
题目是这样的：给你一个链表数组，每个链表都已经按升序排列。请你将所有这些链表合并到一个升序链表中，返回合并后的链表。
举个例子，假设我们有3个链表：
链表 1: 1 -> 4 -> 5
链表 2: 1 -> 3 -> 4
链表 3: 2 -> 6
合并后的结果应该是：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
这道题的难点在于如何高效地合并多个有序链表。如果简单粗暴地一个一个合并，时间复杂度会非常高。那有没有更聪明的方法呢？答案是肯定的！我们有两种高效的解法：分治合并和优先队列。
链表合并基础：从两个到多个的跨越
在深入探讨高级解法之前，我们先来复习一下合并两个有序链表的基本操作。这是解决本题的基础，必须烂熟于心。
合并两个有序链表的思路很简单：
创建一个虚拟头节点(dummy head)，简化边界条件的处理
同时遍历两个链表，比较当前节点的值
将较小的节点接到结果链表上，并移动相应的指针
当一个链表遍历完后，将另一个链表的剩余部分接到结果链表上
下面是合并两个有序链表的代码实现（以Python为例）：
def mergeTwoLists(l1, l2):dummy = ListNode(0)curr = dummywhile l1 and l2:if l1.val < l2.val:curr.next = l1l1 = l1.nextelse:curr.next = l2l2 = l2.nextcurr = curr.nextcurr.next = l1 if l1 else l2return dummy.next
这个函数的时间复杂度是O(n + m)，其中n和m分别是两个链表的长度。空间复杂度是O(1)，因为我们只使用了常数级别的额外空间。
有了合并两个链表的基础，我们自然会想到：能不能通过反复合并两个链表来实现合并K个链表呢？当然可以！但这样做的效率如何呢？
假设每个链表的长度都是n，总共有k个链表。如果我们采用"顺序合并"的策略，即先合并第一个和第二个，再将结果与第三个合并，以此类推，时间复杂度会是多少呢？
第一次合并：O(n + n) = O(2n)
第二次合并：O(2n + n) = O(3n)
...
第k-1次合并：O((k-1)n + n) = O(kn)
总时间复杂度：O(2n + 3n + ... + kn) = O(nk²)。当k很大时（比如k=1000），这个复杂度就太高了！
那有没有更高效的方法呢？当然有！这就是我们接下来要介绍的分治合并算法。
分治合并算法：化繁为简的艺术
分治算法的核心思想是将大问题分解成小问题，解决小问题后再将结果合并。对于合并K个链表的问题，分治策略可以显著提高效率。
分治合并的步骤
分解：将K个链表分成两半，分别合并左半部分和右半部分
解决：递归地合并两个子问题，直到子问题中只剩下一个或两个链表
合并：将子问题的结果合并成最终答案
上图展示了分治合并的过程。可以看到，原本需要合并8个链表的问题，通过分治策略，最终被分解为一系列合并两个链表的子问题。
分治合并的代码实现
下面我们以Python为例，实现分治合并算法：
def mergeKLists(lists):if not lists:return Nonereturn merge(lists, 0, len(lists) - 1)def merge(lists, left, right):if left == right:return lists[left]mid = (left + right) // 2l1 = merge(lists, left, mid)l2 = merge(lists, mid + 1, right)return mergeTwoLists(l1, l2) # mergeTwoLists是前面实现的合并两个链表的函数
分治合并的迭代实现
除了递归，我们也可以用迭代的方式实现分治合并。迭代方法通常使用两两合并的策略，从链表数组的头部开始，每次合并相邻的两个链表，将结果保存回数组，然后继续合并，直到数组中只剩下一个链表。
下面是迭代实现的Python代码：
def mergeKLists(lists):if not lists:return Nonen = len(lists)interval = 1while interval < n:for i in range(0, n - interval, interval * 2):lists[i] = mergeTwoLists(lists[i], lists[i + interval])interval *= 2return lists[0] if n > 0 else None
分治合并的复杂度分析
现在我们来分析一下分治合并的时间复杂度。假设总共有k个链表，每个链表的长度为n。
分治的深度为logk（因为每次都将问题规模减半）
每一层的合并操作总共需要处理O(kn)个节点（因为每一层都有kn个节点需要合并）
因此，总时间复杂度为O(kn logk)
空间复杂度方面：
递归实现：O(logk)（递归调用栈的深度）
迭代实现：O(1)（只使用了常数级别的额外空间）
可以看到，分治合并的时间复杂度比顺序合并的O(kn²)有了显著提升！
优先队列解法：小顶堆的妙用
除了分治合并，我们还可以使用优先队列（小顶堆） 来解决这个问题。这种方法的思路是：
将每个链表的头节点加入小顶堆
每次从堆中取出最小的节点，加入结果链表
如果取出的节点有下一个节点，将其加入堆中
重复步骤2和3，直到堆为空
优先队列解法的代码实现
下面我们用Python实现优先队列解法：
这里有个细节需要注意：我们在堆中存储的是一个元组(节点值, 链表索引, 节点)，而不是直接存储节点。这是因为当两个节点的值相等时，Python的heapq会尝试比较下一个元素。如果我们直接存储节点，当节点值相等时，Python会尝试比较节点对象，这可能会导致错误。加入链表索引可以避免这个问题。
优先队列解法的复杂度分析
时间复杂度：
初始化堆：O(k)（将k个链表的头节点加入堆）
每次堆操作（插入或删除）的时间复杂度是O(logk)
总共有kn个节点需要处理，每个节点需要一次插入和一次删除操作
因此，总时间复杂度为O(kn logk)，与分治合并相同
空间复杂度：
堆中最多存储k个节点，所以空间复杂度为O(k)
多语言实现：Python、Java和JavaScript
为了满足不同语言背景的读者，下面我们分别用Python、Java和JavaScript实现分治合并算法。
Python实现
import heapqdef mergeKLists(lists):dummy = ListNode(0)curr = dummy# 创建优先队列heap = []for i, lst in enumerate(lists):if lst:# 将(节点值, 链表索引, 节点)加入堆，使用链表索引是为了避免节点值相同时的比较错误heapq.heappush(heap, (lst.val, i, lst))while heap:val, i, node = heapq.heappop(heap)curr.next = nodecurr = curr.nextif node.next:heapq.heappush(heap, (node.next.val, i, node.next))return dummy.next
Java实现
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);}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(0);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;}}
JavaScript实现
function ListNode(val, next) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)}/*** @param {ListNode[]} lists* @return {ListNode}*/var mergeKLists = function(lists) {if (lists.length === 0) {return null;}return merge(lists, 0, lists.length - 1);};function merge(lists, left, right) {if (left === right) {return lists[left];}const mid = Math.floor((left + right) / 2);const l1 = merge(lists, left, mid);const l2 = merge(lists, mid + 1, right);return mergeTwoLists(l1, l2);}function mergeTwoLists(l1, l2) {const dummy = new ListNode(0);let curr = dummy;while (l1 && l2) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = l1 || l2;return dummy.next;}
复杂度分析：为什么是O(nlogk)？
我们已经提到过分治合并和优先队列解法的时间复杂度都是O(kn logk)，其中k是链表的数量，n是每个链表的长度。但很多资料上会说这道题的时间复杂度是O(n logk)，这是为什么呢？
其实这两种说法并不矛盾，只是对n的定义不同。如果我们将n定义为所有链表的总节点数，那么时间复杂度就是O(n logk)。因为kn就是总节点数n，所以O(kn logk) = O(n logk)。
我们再来详细推导一下优先队列解法的时间复杂度：
初始化堆：O(k)
总共有n个节点，每个节点需要进行一次入堆和出堆操作
每次堆操作的时间复杂度是O(logk)
因此，总时间复杂度是O(k + n logk) = O(n logk)（当n > k时）
分治合并的时间复杂度也可以类似地推导为O(n logk)。
空间复杂度方面：
分治合并（递归）：O(logk)（递归调用栈）
分治合并（迭代）：O(1)
优先队列：O(k)（堆的大小）
题型拓展：合并K个降序链表
掌握了合并K个升序链表的方法后，我们来思考一个拓展问题：如何合并K个降序链表？
其实很简单，我们有两种思路：
反转链表：先将每个降序链表反转成升序链表，然后使用我们之前讨论的方法合并
修改比较逻辑：在合并过程中，将"取较小节点"改为"取较大节点"
下面我们以分治合并为例，实现合并K个降序链表的功能：
def mergeKDescendingLists(lists):if not lists:return Nonereturn mergeDescending(lists, 0, len(lists) - 1)def mergeDescending(lists, left, right):if left == right:return lists[left]mid = (left + right) // 2l1 = mergeDescending(lists, left, mid)l2 = mergeDescending(lists, mid + 1, right)return mergeTwoDescendingLists(l1, l2)def mergeTwoDescendingLists(l1, l2):dummy = ListNode(0)curr = dummywhile l1 and l2:if l1.val > l2.val: # 这里改为取较大的节点curr.next = l1l1 = l1.nextelse:curr.next = l2l2 = l2.nextcurr = curr.nextcurr.next = l1 if l1 else l2return dummy.next
可以看到，只需要将mergeTwoDescendingLists函数中的比较逻辑从l1.val < l2.val改为l1.val > l2.val即可。
K链表合并流程总结
最后，我们来总结一下合并K个升序链表的完整流程：
问题分析：合并K个升序链表，要求时间复杂度尽可能低
基础思路：合并两个有序链表，时间复杂度O(n + m)
高级解法：
分治合并：将K个链表分成两半，递归合并，时间复杂度O(n logk)，空间复杂度O(logk)（递归）或O(1)（迭代）
优先队列：使用小顶堆每次取最小节点，时间复杂度O(n logk)，空间复杂度O(k)
代码实现：分别用Python、Java和JavaScript实现分治合并算法
复杂度分析：详细推导时间复杂度O(n logk)的由来
拓展思考：如何合并K个降序链表
通过这道题，我们不仅学会了合并K个有序链表的两种高效方法，更重要的是理解了分治算法和优先队列的应用场景。这些思想和方法在解决其他问题时也会经常用到，希望大家能够融会贯通！
如果你对这道题还有什么疑问，或者有更好的解法，欢迎在评论区留言讨论。下次我们将继续讲解LeetCode Hot100的其他经典题目，敬请期待！