LeetCode 23 合并K个有序链表

这道题可以采用类似于归并排序的方式进行解题,一种自顶向下的方法,关键在于partition函数和merge两个函数。partition函数问题的规模大于2就不断的往下分,直至问题的规模小于等于2,当问题的规模为1的话就直接返回那个有序列表单问题的规模为2的话,就用merge函数合并两个列表并返回。

书写代码的过程中需要注意两个事项,

  • 当k等于0的时候,应该直接返回空
  • partition函数的一个边界情况,也需要好好斟酌一下
    • 因为在最终调用partition的时候,[0,len(lists)-1],也就是左闭右闭的一个区间
    • 只当左边界和右边界相同的时候,就直接返回的那个链表就可以,
    • 当左右边左边接小于右边界的时候就要取一个中间值,中间值是两数相加除以2并向下取整,所以厄在求左半边的一个partition结果的时候可以取m,右半边的左边界就要取m加1,因为是 左闭右闭的一个区间,这样也可以保证m不会大于右边界。
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        return self.partition(0, len(lists) - 1, lists)

    def partition(self,start,end,lists):
        # 左闭右闭
        if start == end:
            return lists[start]
        else:
            m = (start + end) // 2
            left = self.partition(start, m, lists)
            right = self.partition(m+1, end, lists)
            return self.merge(left, right)
        
    
    def merge(self, a ,b):
        dummy = tail = ListNode(0)
        while a and b:
            if a.val < b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a if a else b
        return dummy.next

有空可以练习一下非递归自底向上的归并代码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注