合并k个已排序列表

这个题我的解题思路是：

1. 初始化k个指针，形成一个指针列表，这个指针列表用来存放还未排序的各个链表的head；
2. 初始化一个cur指针，这个指针用来存放目前已排序好的链表的表尾；
3. 每次在指针列表中找到val最小的那个指针，然后把cur移到那个指针上，同时该指针后移。
   代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
def getminindex(pheadlist):
    # 返回最小值所在指针的索引
    minindex=-1
    # 初始化
    for i in range(len(pheadlist)):
        if pheadlist[i] != None:
            minindex=i
            break
    if minindex==-1:
        return 0
    for i in range(len(pheadlist)):
        if pheadlist[i] != None:
            if pheadlist[i].val < pheadlist[minindex].val:
                minindex = i
    return minindex

class Solution:
    def mergeKLists(self , lists) -> ListNode:
        # write code here
        k = len(lists)
        if k==0:
            return None
        pheadlist = []
        #新建k个指针
        for i in range(k):
            pheadlist.append(lists[i])
        # 初始化两个指针
        cur=text=ListNode(-1)
        while cur:
            minindex = getminindex(pheadlist)
            cur.next = pheadlist[minindex] # 已完成排序的list的尾部指针后移
            cur=cur.next
            if pheadlist[minindex]!=None:
                pheadlist[minindex] = pheadlist[minindex].next  # 未排序list的指针后移
        return text.next

head1 = ListNode(1) ; head1.next = ListNode(2) ; head1.next.next = ListNode(3)
head2 = ListNode(4) ; head2.next = ListNode(5) 
head = Solution().mergeKLists([head1,head2])
cur=head
while cur:
    print(cur.val)
    cur=cur.next

这个代码应该是正确的，但是只通过了一半的用例，后面报时间复杂度不达标了，我的这个代码应该是O(n2）的，要求是O(nlogn)。
看了下解题思路后，使用最小堆跑了一下成功通过了。这个就很简单了，用python标准库heapq，先把所有的元素构建成最小堆，然后最小堆不断pop构建链表就行。

def mergeKLists(self , lists) -> ListNode:
        # 借助最小堆实现
        minheap = []
        k = len(lists)
        for i in range(k):
            tmphead = lists[i]
            cur = tmphead
            while cur:
                heapq.heappush(minheap,cur.val)
                cur = cur.next
        text = cur = ListNode(-1)
        while len(minheap)>0:
            cur.next = ListNode(heapq.heappop(minheap))
            cur=cur.next
        return text.next

我的牛客网刷题记录，基本上都会把题目的解题代码放到上面，一些比较复杂或有意思的会在csdn专门写一下，其他简单的就直接在牛客网记录啦。