【题目】
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入： lists = [[1,4,5],[1,3,4],[2,6]]
输出： [1,1,2,3,4,4,5,6]
解释： 链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入： lists = []
输出： []
示例 3：
输入： lists = [[]]
输出： []
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4-
lists[i]按 升序 排列 -
lists[i].length的总和不超过10^4
【题目解析】
思路：
合并 K 个有序链表的问题可以通过多种方法解决。最常用的方法包括逐一比较、优先队列（最小堆）和分治合并。这里，我们重点介绍分治合并方法，它是一种高效且实现简单的策略。
-
逐一比较：
- 一次比较所有链表的头节点，并将最小节点连接到合并后的链表上。
- 这个过程需要重复进行，直到所有链表都为空。
- 这种方法的时间复杂度是 O(kn)，其中
k是链表的数量，n是所有链表中节点的总数。
-
优先队列：
- 使用优先队列（最小堆）来优化上述逐一比较的过程。
- 将每个链表的头节点放入优先队列中，每次从中取出最小节点，并将取出节点的下一个节点放入队列中。
- 这种方法的时间复杂度可以降低到 O(nlogk)。
-
分治合并：
- 类似于归并排序中的合并过程，两两合并链表，直到只剩下一个链表。
- 这种方法的时间复杂度也是 O(nlogk)，并且常数因子较小，通常比使用优先队列更快。
下面是使用分治合并方法的示例代码：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
l1 = lists[I]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
mergedLists.append(self.mergeTwoLists(l1, l2))
lists = mergedLists
return lists[0]
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
执行：
【总结】
适用问题类型： 合并 K 个有序链表的问题是数据结构和算法领域中的一个常见问题，特别适合于处理多个有序数据序列的场景。这种问题类型不仅限于链表，也适用于任何需要整合、合并多个有序序列的情况，如合并多个有序数组、时间线事件、排好序的数据流等。这类问题的共同特点是涉及到多个已排序的数据结构，且需要以有效的方式将它们合并为一个单一的、有序的数据结构。
使用的算法： 解决合并 K 个有序链表问题的主要算法是分治法。分治法是一种将问题分解成多个较小、相似的子问题，分别解决这些子问题，然后将解决方案组合以解决原始问题的技术。在本问题中，分治法被用于两两合并链表，每次合并减少一半的链表，直到剩下一个链表。
算法细节：
- 分解子问题：将 K 个链表分为两部分，每部分包含一半的链表。
- 递归解决：递归地对每部分应用同样的分治策略，直至每部分只剩下一个链表或没有链表。
- 合并解决方案：合并每一步递归返回的两个链表，直到所有链表被合并成一个链表。
算法性能： 分治法在合并 K 个有序链表问题中的时间复杂度是 O(NlogK)，其中 N 是所有链表中元素的总数，K 是链表的数量。这是因为每次合并操作都需要遍历两个链表的长度，而每一层递归大约减少一半的链表。空间复杂度主要取决于递归时栈的使用，为 O(logK)。
总结与扩展： 合并 K 个有序链表的问题展示了分治法在解决实际问题中的应用。这种方法不仅适用于链表，也可以扩展到其他类型的数据结构，如数组。此外，它还提供了一种有效处理多个数据源的模式，这在数据库操作、外部排序、多路归并等领域中非常有用。掌握分治法对于解决复杂问题是非常重要的，它不仅能帮助我们在算法面试中脱颖而出，也对日常软件开发中的问题解决有极大的帮助。
