用python语言解答LeetCode的23题
官方题解里面给了五种解法，第一次写博客应该不会把五种都搞懂，会先学习里面的两种，一刷主要学习了方法一和方法三。二刷的时候会补齐其他思路。
- 方法一：暴力解法
- 方法二：逐一比较
- 方法三：用优先队列优化方法二
- 方法四：逐一两两合并链表
- 方法五：分治法
碎碎念（不用看！下一节开始才是重点~~~）
以为做过第21题思路就可以打开，还是图样图森破，唉，还是得多学习呀
官方题解里面给了五种解法，第一次写博客应该不会把五种都搞懂，会先学习里面的两种，二刷的时候会补齐其他思路。
方法一：暴力解法
这个思想很简单，意思就是先将链表都转化为数组，将数组中的元素进行排序，之后将排好序的数组转化为链表并返回结果。
- 遍历所有链表，将所有节点的值放到一个数组中
- 将这个数组排序，然后遍历所有元素得到正确顺序的值
- 用遍历得到的值，创建一个新的有序链表。
这个思想里面的第二步中排序方法也是值得深究的，这里先作为遗留问题，后面遇到这种类型的题会重点分析。
由于用的是Python语言，所以就直接用它内置的排序函数sorted()啦
方法一的代码：
# 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
self.nodes = []
head = point = ListNode(0)
for l in lists
while l
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes)
point.next = ListNode(x)
point = point.next
return head.next
方法一的运行结果：
方法二：逐一比较
感觉第二个方法的思路也比较暴力，它的思路如下：
- 第一步：比较k个节点（每个链表的首节点），获得最小值的节点
- 第二步：将选中的节点接在最终有序链表的后面
怎么感觉和合并两个有序链表时的方法很神似
方法三：用优先队列优化方法二
第三个方法和第二个方法的思路是一样的，区别是将比较环节用优化队列进行了优化。
先解释一下什么是优先队列：
我们都知道普通的队列是一种先进先出的数据结构，元素在队列尾部追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。
优先队列分两种情况：
- 第一种：最大优先队列，无论入队顺序，当前最大的元素优先出队
- 第二种：最小优先队列，无论入队顺序，当前最小的元素优先出队
这里遇到了很多问题，太长了，写成了番外篇(一)，详情请见下一篇博客
方法三的代码：
#codingutf-8
from queue import PriorityQueue
class ListNode()
def __init__(self, x)
self.val = x
self.next = None
class Solution()
def mergeKList(self, lists)
param lists ListNode
return ListNode
head = point = ListNode(0)
q = PriorityQueue()
##############修改部分##########
for index, l in enumerate(lists)
if l
q.put((l.val, index, 0, l)) # 存ListNode.val，链表序号，链表中的元素下标，ListNode
###############################
while not q.empty()
##############修改部分##########
val, id, index, node = q.get()
##############修改部分##########
point.next = ListNode(val)
point = point.next
node = node.next
if node
##############修改部分##########
q.put((node.val, id, index + 1, node))
##############修改部分##########
return head.next
方法三的运行结果：
方法四：逐一两两合并链表
第四个方法的解题思想是：将合并K个链表的问题转化为合并2个链表k-1次
方法五：分治法
第五个方法沿用了第四个方法的解题思路，但是进行了较大的优化，我们不需要对大部分节点重复遍历多次。
- 将k个链表配对并将同一对中的链表合并
- 第一轮合并以后，k个链表被合并成k2个链表，平均长度为2Nk,然后是k4个链表，k8个链表等等
- 重复这一过程，直到我们得到了最终的有序链表。
因此，我们在每一次配对合并的过程中都会遍历几乎全部N个节点，并重复这一过程log2K次
Reference：
- 什么是优先队列httpwww.sohu.coma256022793_478315
- Python的四种内置队列httpswww.cnblogs.comcmnzp6936181.html
