T23 合并K个升序链表

题目描述如下：

解题思路：每次从这几个链表中选择一个最小的值，加入到head值指向的合并链表的链表尾部，选择完毕就令当前被选择的结点（在被选择的升序链表中）指向下一个next结点，并进行下一轮的比较。如果其中有一个升序链表先被选完了，就将该None值pop掉，直到所有的升序链表都被选择完毕且被pop掉时，就得到了合并后的链表结果。

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        listp = [lists[i] for i in range(k)]
        head = None
        pnode_pre = None

        #排除掉空列表的情况
        for i in range(k-1,-1,-1):
            if listp[i] is None:
                listp.pop(i)

        # 还有结点可以选择的话
        while listp!=[]:
            # 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
            minval = listp[0].val
            index = 0
            for i in range(1,len(listp)):
                if minval > listp[i].val:
                    minval = listp[i].val
                    index = i
            if listp[index].next is None:
                listp.pop(index)
            else:
                listp[index] = listp[index].next
            
            # 前一个结点指向新建的节点
            node = ListNode(minval, None)
            if head is None: 
                head = node
                pnode_pre = node
            else:
                pnode_pre.next = node
                pnode_pre = node

        return head

结果如下：

看到结果发现是真的慢，想了想发现有很多可以优化的地方：

空间复杂度上：

首先不需要使用listp来进行存储，题目中给的就是listp列表的作用

同时，也不需要再次建立一个Linknode对象，直接使用输入中链接的就可以。

试了一下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        head = None
        pnode_pre = None

        #排除掉空列表的情况
        for i in range(k-1,-1,-1):
            if lists[i] is None:
                lists.pop(i)
                
        # 还有结点可以选择的话
        while lists!=[]:
            # 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
            minval = lists[0].val
            index = 0
            for i in range(1,len(lists)):
                if minval > lists[i].val:
                    minval = lists[i].val
                    index = i
            if lists[index].next is None:
                node = lists.pop(index)
            else:
                node = lists[index]
                lists[index] = lists[index].next          
            # 前一个结点指向新建的节点
            if head is None: 
                head = node
                pnode_pre = node
            else:
                pnode_pre.next = node
                pnode_pre = node

        return head

结果空间复杂度降下去了：

时间复杂度上，应该要减少比较的次数，如果每次都需要从k个结点中选择一个最小的，确实难以减少比较次数，所以想着做类似于合并排序算法，两个两个一组排序再合并。

转念一想，最后要的是所有值的最终的排序，那我直接把所有值得到后再排序岂不是更快？

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        allnum = []
        for i in range(len(lists)):
            while lists[i] is not None:
                allnum.append(lists[i].val)
                lists[i] = lists[i].next
        allnum.sort()
        head = None
        pnode_pre = None
        for i in range(len(allnum)):
            node = ListNode(allnum[i], None)
            if head is None:
                head = node
                pnode_pre = node
                continue 
            pnode_pre.next = node
            pnode_pre = node
        return head

结果如下：

有点钻空子的嫌疑哈哈哈哈哈哈c