栈和队列_leetcode23

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        res = []
        for i in lists:
            while i:
                res.append(i.val)
                i = i.next
        if res == []:
            return []
        res.sort()
        l = ListNode(0)
        first = l
        while res:
            l.next = ListNode(res.pop(0))
            l = l.next
        return first.next

# 优先队列
# 复杂度
#
# 时间 O(NlogK) 空间 O(K)
# 思路
#
# 当我们归并k个列表时，最简单的方法就是，对于每次插入，我们遍历这K个列表的最前面的元素，找出K个中最小的再加入到结果中。
# 不过如果我们用一个优先队列（堆），将这K个元素加入再找堆顶元素，每次插入只要logK的复杂度。
# 当拿出堆顶元素后，我们再将它所在链表的下一个元素拿出来，放到堆中。这样直到所有链表都被拿完，归并也就完成了。