23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution: Heap

import heapq


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        q = [(node.val, node) for node in lists if node]
        heapq.heapify(q)
        cur = dummy = ListNode(None)
        while q:
            _, node = q[0]
            cur.next = node
            cur = node
            if node.next:
                heapq.heapreplace(q, (node.next.val, node.next))
            else:
                heapq.heappop(q)
        return dummy.next

Lessons:

• heapreplace is faster than heappop, because the size of heap does not change.
• Use heappushpop instead of heapreplace, when the new pushed value could be smaller than the popped.