-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0023_MinHeap.py
36 lines (35 loc) · 1.17 KB
/
Leetcode0023_MinHeap.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
import heapq
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return None
# each time we append the smallest node from lists
# we just need tro choose the smallest from each starting node from each sorted list
minHeap = []
# initialize the min-heap
for i in range(len(lists)):
if lists[i]:
heapq.heappush(minHeap, (lists[i].val,lists[i]))
dummyHead = ListNode(0)
p = dummyHead
while(minHeap):
# pop out the minimum
minNode = heapq.heappop(minHeap)[1]
# get the next node of minNode and push it into the heap
nextNode = minNode.next
if nextNode:
heapq.heappush(minHeap, (nextNode.val, nextNode))
# add the minNode to the dummy head
p.next = minNode
p = p.next
p.next = None
return dummyHead.next