23. Merge K Sorted Lists

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

solution

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # ListNode.__lt__ = lambda self, other: self.val < other.val  # 最简洁的做法是增加属性, 可以把node直接push进heap

        heap = []
        for i, l in enumerate(lists):
            # 注意: 只有每个list的head进入heap
            if l:
                heapq.heappush(heap, (l.val, i, l))  # python3 heap中前一个相等就会判断下一个, 因此想要把node进入heap, 需要3个元素或index

        dummy = head = ListNode()
        while heap:
            val, i, node = heapq.heappop(heap)            
            head.next = node
            head = head.next

            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))                

        return dummy.next

时间复杂度：O(nklog k) 空间复杂度：O(k)

follow up

88. Merge Sorted Array

632. Smallest Range Covering Elements from K Lists