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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
'''
class Solution:

    # 合并两个链表
    def Merge2(self,head1:ListNode,head2:ListNode)->ListNode:
        if not head1 or not head2:
            return head2 or head1
        if head1.val>head2.val:  
            head2.next=self.Merge2(head1,head2.next)
            return head2
        else:
            head1.next=self.Merge2(head1.next,head2)
            return head1

    # 划分合并区间函数
    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.Merge2(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)
'''
import sys
#设置递归深度
sys.setrecursionlimit(100000) 

class Solution:
    #两个有序链表合并函数
    def Merge2(self, pHead1: ListNode, pHead2: ListNode) -> ListNode: 
        #一个已经为空了，直接返回另一个
        if pHead1 == None: 
            return pHead2
        if pHead2 == None:
            return pHead1
        #加一个表头
        head = ListNode(0) 
        cur = head
        #两个链表都要不为空
        while pHead1 and pHead2: 
            #取较小值的节点
            if pHead1.val <= pHead2.val: 
                cur.next = pHead1
                #只移动取值的指针
                pHead1 = pHead1.next 
            else:
                cur.next = pHead2
                #只移动取值的指针
                pHead2 = pHead2.next 
            #指针后移
            cur = cur.next 
        #哪个链表还有剩，直接连在后面
        if pHead1: 
            cur.next = pHead1
        else:
            cur.next = pHead2
        #返回值去掉表头
        return head.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.Merge2(self.divideMerge(lists, left, mid), self.divideMerge(lists, mid + 1, right))
    
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        #k个链表归并排序
        return self.divideMerge(lists, 0, len(lists) - 1)