# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# the head of the merged array.
head = ListNode(None)
curr = head
heap = []
#FOR CODING
# The real representaion is a little differnet from usual arrays in Lists
# Percieved : [[1,4,5],[1,3,4],[2,6]]
# actual : lists = [ 1->tail, 1->tail, 2-> tail ]
for i in range(len(lists)):
#if the head is not none.
if lists[i]:
#pushIntoHeap(heads of the lists, index of the head)
heapq.heappush(heap,(lists[i].val,i))
# change the value of the heads to the next item.
lists[i] = lists[i].next
#heap looks like this [(1, 0), (1, 1), (2, 2)]
# while there are some elements left in the heap, this emulates multiple pointers
while heap:
# pop the min elemnet out with the index of the array it was pushed from
val, index = heapq.heappop(heap)
#create a new node
curr.next = ListNode(val)
# Add it to the merged List and move the curr along
curr = curr.next
#add from the linkedList for which the element was pushed out of.
if lists[index]:
heapq.heappush(heap,(lists[index].val,index))
lists[index] = lists[index].next
return head.next