Merge K Sorted Lists

Heap
Hard

Approach

Diagrams

Analysis

Time

Space

from queue import PriorityQueue

class Solution():
    def mergeKLists(self, lists):
        pseudoHead = ListNode(None)
        cur = pseudoHead
        
        priorityQueue = PriorityQueue()

        for listIdx, node in enumerate(lists):
            self.addNodeToPriorityQueue(node, listIdx, priorityQueue)

        while not priorityQueue.empty():
            nodeVal, listIdx, node = priorityQueue.get()
            self.addNodeToPriorityQueue(node.next, listIdx, priorityQueue)
            node.next = None
            cur.next = node
            cur = cur.next

        return pseudoHead.next
    
    def addNodeToPriorityQueue(self, node, nodeIdx, priorityQueue):
        if node:
            priorityQueue.put((node.val, nodeIdx, node))

Learn

#Priority Queue

Videos