23. 合并K个升序链表(Hard)

题目描述

合并K个升序链表

样例

Input：lists = [[1,4,5],[1,3,4],[2,6]]
Output：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解题思路

本质上就是通过递归不停地 合并两个有序链表

从代码上和 109. 有序链表转换二叉搜索树(Medium) 一样

Python示例

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoList(l1, l2):
            dummpyHead = ListNode(None)
            p = dummpyHead
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1 
                    l1 = l1.next
                else:
                    p.next = l2 
                    l2 = l2.next
                p = p.next 
            p.next = l1 if l1 else l2
            return dummpyHead.next 
        
        if not lists: return
        if len(lists) == 1: return lists[0] # 只有一个就不用排了
        # 递归排
        mid =  len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return mergeTwoList(left, right)