刷题记录：合并k个已排序的链表

有一说一，看完题目后我还没想好怎么做

我最初的想法是：对列表进行遍历，找出最小的结点加入新链表中，直到列表中不存在结点
但这样的话时间复杂度就不满足要求了

然后我瞥见知识点：堆
堆！堆……堆？
一个程序员有一个问题要解决，他准备用多线程来做，现在他有两个问题了
有一说一堆我基本上忘干净了😢

然后我又看见了分治
分治！……分治？
哦哦哦哦哦哦归并归并！！！

说真的，如果没想起归并排序我估计还得卡更久
代码如下：

def mergeKLists(self , lists: List[ListNode]) -> ListNode:
    lists_len = len(lists)
    if lists_len == 1:      # 如果列表里仅有一链表，则返回
        return lists[0]
    if lists_len >= 2:      # 如果有两个以上，则接着分
        left_list = self.mergeKLists(lists[0:lists_len // 2])
        right_list = self.mergeKLists(lists[lists_len // 2:])
        return self.Merge(left_list, right_list)    # 合并链表并返回
      
    return None


def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
    if pHead1 == None:
        return pHead2
    if pHead2 == None:
        return pHead1
    
    head = ListNode(0)
    cur = head
    while pHead1 != None and pHead2 != None:
        if pHead1.val <= pHead2.val:
            cur.next = pHead1
            pHead1 = pHead1.next
        else:
            cur.next = pHead2
            pHead2 = pHead2.next
        cur = cur.next
            
    if pHead1 == None:
        cur.next = pHead2
    else:
        cur.next = pHead1
    
    return head.next

为啥 Merge() 没注释嘞？
因为是从合并两个排序的链表cv过来的