merge_k_sorted_lists
1from typing import Optional 2from utils import ListNode 3from heapq import heapify, heappush, heappop 4 5 6# @leet start 7class Solution: 8 def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]: 9 """ 10 To merge K sorted lists, we can first put all of the head node vals of the list 11 into a heap, along with their indices. 12 13 While we have items in our heap, we construct a list by popping the minimum 14 value from the heap and then adding a new value from the list that we 15 popped from, using the index provided alongside the heap. 16 17 At the end, we return the resulting list. 18 """ 19 20 dummy = ListNode() 21 curr = dummy 22 23 heap = [] 24 25 for index, l in enumerate(lists): 26 if l is not None: 27 heap.append((l.val, index)) 28 lists[index] = lists[index].next 29 30 heapify(heap) 31 32 while heap: 33 min_val, index = heappop(heap) 34 curr.next = ListNode(min_val) 35 curr = curr.next 36 37 if lists[index] is not None: 38 heappush(heap, (lists[index].val, index)) 39 lists[index] = lists[index].next 40 41 return dummy.next 42 43 44# @leet end 45 46 47def test(): 48 assert 2 + 2 == 4
class
Solution:
8class Solution: 9 def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]: 10 """ 11 To merge K sorted lists, we can first put all of the head node vals of the list 12 into a heap, along with their indices. 13 14 While we have items in our heap, we construct a list by popping the minimum 15 value from the heap and then adding a new value from the list that we 16 popped from, using the index provided alongside the heap. 17 18 At the end, we return the resulting list. 19 """ 20 21 dummy = ListNode() 22 curr = dummy 23 24 heap = [] 25 26 for index, l in enumerate(lists): 27 if l is not None: 28 heap.append((l.val, index)) 29 lists[index] = lists[index].next 30 31 heapify(heap) 32 33 while heap: 34 min_val, index = heappop(heap) 35 curr.next = ListNode(min_val) 36 curr = curr.next 37 38 if lists[index] is not None: 39 heappush(heap, (lists[index].val, index)) 40 lists[index] = lists[index].next 41 42 return dummy.next
9 def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]: 10 """ 11 To merge K sorted lists, we can first put all of the head node vals of the list 12 into a heap, along with their indices. 13 14 While we have items in our heap, we construct a list by popping the minimum 15 value from the heap and then adding a new value from the list that we 16 popped from, using the index provided alongside the heap. 17 18 At the end, we return the resulting list. 19 """ 20 21 dummy = ListNode() 22 curr = dummy 23 24 heap = [] 25 26 for index, l in enumerate(lists): 27 if l is not None: 28 heap.append((l.val, index)) 29 lists[index] = lists[index].next 30 31 heapify(heap) 32 33 while heap: 34 min_val, index = heappop(heap) 35 curr.next = ListNode(min_val) 36 curr = curr.next 37 38 if lists[index] is not None: 39 heappush(heap, (lists[index].val, index)) 40 lists[index] = lists[index].next 41 42 return dummy.next
To merge K sorted lists, we can first put all of the head node vals of the list into a heap, along with their indices.
While we have items in our heap, we construct a list by popping the minimum value from the heap and then adding a new value from the list that we popped from, using the index provided alongside the heap.
At the end, we return the resulting list.
def
test():