合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
超时！
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists) <= 0:
return None
dummy = ListNode(0)
p = dummy
flag = True
while flag:
flag = False
_dict = {}
for i, node in enumerate(lists):
if node:
flag = True
_dict[i] = node.val
_min = 0x7fffffff
key = 0
for k, v in _dict.items():
if v < _min:
_min = v
key = k
p.next = lists[key]
p = p.next
if lists[key]:
lists[key] = lists[key].next
return dummy.next
Solution 1 字典记录值和node，列表记录值并排序，64ms
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
ret = []
maps = {}
for x in lists:
next = x
while next:
if next.val not in maps:
ret.append(next.val)
maps[next.val] = [next]
else:
maps[next.val] += [next]
next = next.next
ret.sort()
head = None
next = None
for i in ret:
v = maps[i]
if head is None:
head = v[0]
next = head
v = v[1:]
for j in v:
next.next = j
next = j
return head
Solution 2 优先队列，堆，184ms
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
dummy = ListNode(None)
curr = dummy
q = PriorityQueue()
for node in lists:
if node: q.put((node.val,node))
while q.qsize()>0:
t=q.get()
curr.next = t[1]
curr=curr.next
if curr.next: q.put((curr.next.val, curr.next))
return dummy.next
