Skip to content

023 merge k sorted lists

23. Merge k Sorted Lists

题目: https://leetcode.com/problems/merge-k-sorted-lists/

难度: Hard

思路:

看到思路有heap,similar question有ugly number|| -> 这个是用heapq来解决的

那么就用heap吧? heapsort

最简单的做法是只要每个list里面还有node,就把他们扔到minheap里面去,然后再把minheap pop,一个一个node连起来,听起来时间复杂度和空间复杂度都蛮高的。 直接merge必然是不好的,因为没有利用有序这个点,应该做的是每次取来一个,然后再把应该的下一个放入

写到这里瞬间明白和ugly number ii像的点了,甚至感觉跟find in sorted matrix ii也像

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq
        h = []
        for lst_head in lists:
            if lst_head:
                heapq.heappush(h, (lst_head.val, lst_head))
        cur = ListNode(-1)
        dummy = cur
        while h:
            smallest_node = heapq.heappop(h)[1]
            cur.next = smallest_node
            cur = cur.next
            if smallest_node.next:
                heapq.heappush(h, (smallest_node.next.val, smallest_node.next))
        return dummy.next

当然还像merge two sorted list



回到顶部