# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param lists ListNode类一维数组 # @return ListNode类 # class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if len(lists) == 0: return None if len(lists) == 1: return lists[0] # 分治:将问题转换为第1个链表与k-1个链表合并的问题 return self.merge(lists[0], self.mergeKLists(lists[1:])) # 合并两个有序链表 def merge(self, list1: ListNode, list2: ListNode) -> ListNode: if list1 == None: return list2 if list2 == None: return list1 if list1.val < list2.val: list1.next = self.merge(list1.next, list2) return list1 if list1.val >= list2.val: list2.next = self.merge(list2.next, list1) return list2