Hard
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed104.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from queue import PriorityQueue
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
class Wrapper():
def __init__(self, node):
self.node = node
def __lt__(self, other):
return self.node.val < other.node.val
q = PriorityQueue()
for l in lists:
if l:
q.put(Wrapper(l))
senti = ListNode(0)
head = senti
while not q.empty():
node = q.get().node
head.next = node
head = head.next
if node.next:
q.put(Wrapper(node.next))
return senti.next
# heap = []
# heapq.heapify(heap)
# for l in lists:
# head = l
# while head:
# heapq.heappush(heap, head.val)
# head = head.next
# senti = ListNode(0)
# head = senti
# while heap:
# head.next = ListNode(heapq.heappop(heap))
# head = head.next
# return senti.next