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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:  
    dummy = ListNode(0)  # 创建哑节点  
    current = dummy  
  
    while l1 and l2:  
        if l1.val < l2.val:  
            current.next = l1  
            l1 = l1.next  
        else:  
            current.next = l2  
            l2 = l2.next  
        current = current.next  
  
    # 如果l1还有剩余节点，将它们添加到新链表的末尾  
    current.next = l1 if l1 else l2  
  
    return dummy.next  # 返回合并后链表的头节点 

class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        if not lists:  
            return None  
    
        # 当链表列表只剩下一个或没有时，直接返回  
        if len(lists) == 1:  
            return lists[0]  
    
        # 将链表列表两两分组  
        mid = len(lists) // 2  
        left_half = self.mergeKLists(lists[:mid])  
        right_half = self.mergeKLists(lists[mid:])  
    
        # 合并两个已排序的链表  
        return merge_two_lists(left_half, right_half)