本篇博客主要记录在使用官方题解的方法三解决LeetCode23合并K个顺序链表时遇到的问题，以及解决问题的过程。
先来回顾一下方法三的解题思路：
第一步：用优先队列比较K个节点（每个链表的首节点），获得最小值的结点
第二步：将选中的节点接在最终有序链表的后面
先解释一下什么是优先队列：
我们都知道普通的队列是一种先进先出的数据结构，元素在队列尾部追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。
官网题解代码
#coding:utf-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 l in lists:
if l:
q.put((l.val, l))
while not q.empty():
val, node = q.get()
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.next
遇到问题一：
TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
heappush(self.queue, item)
Line 227 in _put (/usr/lib/python3.6/queue.py)
self._put(item)
Line 143 in put (/usr/lib/python3.6/queue.py)
Line 16 in mergeKLists (Solution.py)
Line 48 in _driver (Solution.py)
Line 61 in <module> (Solution.py)
这个是因为如果有两个节点的val相同，那优先队列会比较二元组的第二个元素，也就是该结点，但是该结点是不可以比较的，因此会得到一个错误TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'。
官方解答下面的讨论去也有同学遇到了这个问题，他的解决方案使新建了一个可比较的类，重写了lt函数来实现自定义比较。（这个目前不会实现）
有位大佬给了解决方案
for index, node in enumerate(lists):
if node:
q.put((node.val, index, node)) #index是绝对不可能重的
于是我改了一下代码：
#coding:utf-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, l))
###############################
while not q.empty():
val, node = q.get()
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.next
按照上述方法解决问题一之后又遇到了问题二
问题二：
ValueError: too many values to unpack (expected 2)
Line 19 in mergeKLists (Solution.py)
Line 48 in _driver (Solution.py)
Line 61 in <module> (Solution.py)
too many values to unpack (expected 2)这种错误是指一个tuple值赋给另一个tuple变量时，变量个数不够造成的，例如图：
修改一下问题就解决了：
用同样的方法解决这个问题，修改代码如下：
#coding:utf-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, l))
###############################
while not q.empty():
##############修改部分##########
val, index, node = q.get()
###############################
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.next
你以为问题就解决了？图样图森破，它又报错。。。
问题三：
ValueError: not enough values to unpack (expected 3, got 2)
Line 19 in mergeKLists (Solution.py)
Line 48 in _driver (Solution.py)
Line 61 in <module> (Solution.py)
然后我就是这样的：
又折腾了一会儿发现还是不行，去吃饭了。。。
我找到解决方案啦~~~~还是在评论区里，有位大佬给的解决方案
我看了一遍，木有照着改，而是把我上面的代码又进行了一次修改：
#coding:utf-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, l))
###############################
while not q.empty():
##############修改部分##########
val, index, node = q.get()
##############修改部分##########
point.next = ListNode(val)
point = point.next
node = node.next
if node:
##############修改部分##########
q.put((node.val, index, node))
##############修改部分##########
return head.next
这是执行结果：
原以为大功告成了。。。提交之后并木有通过。。。还是有bug。。。简直是人生的大起大落。。。
TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
heappush(self.queue, item)
Line 227 in _put (/usr/lib/python3.6/queue.py)
self._put(item)
Line 143 in put (/usr/lib/python3.6/queue.py)
Line 24 in mergeKLists (Solution.py)
Line 48 in _driver (Solution.py)
Line 61 in <module> (Solution.py)
还是乖乖的按照上面大佬给代码修改一下：
#coding:utf-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
提交之后运行通过啦~~哇咔咔咔~~
具体原理的话，我现在也解释不清楚，每篇博客都有遗留问题。。。。不过这样再次看的时候才好优化嘛~~~
Reference：
1.什么是优先队列
http://www.sohu.com/a/256022793_478315
2.LeetCode官方题解
https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode/
