Leetcode Problem 23 Merge k Sorted Lists.txt

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6


Hint: Use priority queue to merge the sorted list

import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        
        myPQ = []
        
        for linkedList in lists:
            while linkedList != None:
                heapq.heappush(myPQ, linkedList.val)
                linkedList = linkedList.next
        
        if len(myPQ) > 0:
            node = ListNode(heapq.heappop(myPQ))
            head = node
            while len(myPQ) > 0:
                createdNode = ListNode(heapq.heappop(myPQ))
                node.next = createdNode
                node = createdNode
            return head
        else:
            dummyNode = ListNode(0)
            return dummyNode.next