题解 | #合并k个已排序的链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    """思路1 归并排序思想
    双指针；分治将大而复杂的问题划分成多个性质相同但规模更小的子问题，子问题继续划分，知道问题解决。

    归并排序：将数组每次划分成登场的两个部分，对两部分进行排序。
        终止条件：划分时左右区间相等或左边大于右边
        返回值：    每次返回已经合并好的子问题链表
        本级任务：对半划分，将划分后的子问题合并成新的链表
    1.链表的首尾开始，每次从中间划分，划分成两半，得到左边n/2 的链表和右边n/2的链表
    2.递归划分至每部分链表为1
    3.划分好的相邻两部分链表有序合并，

    """

    # 两个有序链表合并
    def merge_t(slef,pHead_1: ListNode, pHead_2:ListNode) ->ListNode:
        # 一个为空，返回另一个
        if pHead_1 == None:
            return pHead_2
        if pHead_2 == None:
            return pHead_1

        # 加一个表头
        res = ListNode(0)
        cur = res
        # 两个链表都要不为空
        while pHead_1 and pHead_2:
            # 取较小值的节点
            if pHead_1.val<=pHead_2.val:
                cur.next = pHead_1
                # 之移动取值的指针
                pHead_1 = pHead_1.next
            else:
                cur.next = pHead_2
                # 之移动取值的指针
                pHead_2  = pHead_2.next
            # 指针后移
            cur = cur.next
        # 哪个链表还有剩，连到后面
        if pHead_1:
            cur.next = pHead_1
        else:
            cur.next = pHead_2
        # 返回值去掉表头
        return res.next

    # 划分合并区间函数
    def divideMerge(self,lists:List[ListNode],left:int,right:int)->ListNode:
        if left > right:
            return None
        # 中间一个的情况
        elif left == right:
            return lists[left]
        # 中间分两段，再将合并好的两端合并
        mid = (int)((left+right)/2)
        return self.merge_t(self.divideMerge(lists,left,mid), self.divideMerge(lists,mid+1,right))

    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here 
        return self.divideMerge(lists,0,len(lists) -1)

一脸懵逼