题目
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
此学习笔记，参考题解：
感谢！！
优先队列
依靠最小堆的特性，每次弹出必定是最小值
堆排序
步骤：
- 将所有节点的加入到堆队列中
- 不断弹出，生成新的链表
说明： 在python中，我们默认创建的实例之间不能使用 比较运算符 进行比较，是因为没有重写比较方法
__lt__,__gt__,__le__,__ge__,__eq__所以可以重写
__lt__方法，使得〔ListNode实例〕之间可以大小比较def __lt__(self, other): return self.val < other.val ListNode.__lt__ = __lt__
完整代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists: return None
import heapq
queue = []
dummy = ListNode(-1)
def __lt__(self, other):
return self.val < other.val
ListNode.__lt__ = __lt__
cur = dummy
# 将所有节点加入至堆队列中
for l in lists:
while l:
heapq.heappush(queue, l)
l = l.next
# 不断取出节点
while queue:
# 由于最小堆的特性，每次取出的节点都是最小的
node = heapq.heappop(queue)
cur.next = node
cur = cur.next
cur.next = None
return dummy.next
空间复杂度： O(N)
堆排序优化
此方法是对上一方法的优化，在上面方法中是直接将所有的节点一股脑全部丢到堆队列中，这造成了空间的浪费。在此，可以将空间复杂度优化成O(K)，即链表的数量
将每个链表的头结点，加入到堆队列即可，当此节点出队列时，立即判断此节点的指针域是否为空，不为空就表示后面还有节点，所以将后面的节点加入到堆队列中。如此一来，堆队列的空间大小就没有发生变换。
步骤：
- 将所有链表的头节点加入到堆队列中
- 出队，将出来的节点连接到新节点上
dummy - 检测刚出队的节点的指针域是否有效，有效则将下一个节点加入到堆队列中
完整代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def __lt__(self, other):
return self.val < other.val
ListNode.__lt__ = __lt__
if not lists:
return
import heapq
queue = []
dummy = ListNode(-1)
cur = dummy
# 将所有的链表的头结点入队
for i in range(len(lists)):
head = lists[i]
if head:
heapq.heappush(queue, head)
# 从堆队列中弹出并检测是否还有下一个节点，有则加入到堆队列中
while queue:
node = heapq.heappop(queue)
cur.next = node
cur = cur.next
# 下一个节点是否有效
if node.next:
heapq.heappush(queue, node.next)
cur.next = None
return dummy.next
两两合并
[简单]合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/
之前做过一道题，实现两个有序链表的合并
本题是多个有序链表的合并，所以自然可以使用使用两两合并，合并到最后即成为一个有序链表
完整代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
dummy = ListNode(float('-inf'))
cur = dummy
for i in range(len(lists)):
cur = self.mergeTwoLists(cur, lists[i])
return dummy.next
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
然而，效率极低
分治法
在排序算法中，一个〔归并排序〕
将无序的序列分解成一个一个，然后按有序方式组合
归并排序中的 分治思想 可以在此题应用到
按照归并排序的案例或上图的演示，我们首先将 lists 中的链表一分再分， 然后按照大小关系一一合并
步骤：
- 将 lists 一分再分，分到不能再分为止
- 不断合并
- 最后得到完整的有序链表
步骤描述只是大概，具体还是得根据代码来慢慢理解，所以一定要写注释！！！
完整代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists: return
return self.merge(0, len(lists)-1, lists)
def merge(self, left, right, lists):
"""将lists不断分割，这里的操作有点像二分法
通过不断的一分二，分到最小单位
"""
if left == right:
return lists[left]
mid = (left + right) >> 1
l1 = self.merge(left, mid, lists)
l2 = self.merge(mid+1, right, lists)
# 调用合并函数，将 l1 和 l2合并成新有序链表
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
"""将两个链表合成一个有序链表"""
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next