Merge K Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Tags: Heap, Linked List
Try It!
Discussion
Video
Solution
Simple solution creating new nodes
import heapq
# 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[ListNode]) -> ListNode:
min_heap = []
for node in lists:
while node != None:
heapq.heappush(min_heap, node.val)
node = node.next
dummy = ListNode("dummy")
cur = dummy
while min_heap:
min_val = heapq.heappop(min_heap)
cur.next = ListNode(min_val)
cur = cur.next
return dummy.next
Reuse nodes fix comparison with Monkey Patching and remove cycles
import heapq
# 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]:
ListNode.__lt__ = lambda self, other: self.val < other.val
max_heap = []
for node in lists:
while node:
heapq.heappush(max_heap, node)
node = node.next
dummy = ListNode()
cur = dummy
while max_heap:
node = heapq.heappop(max_heap)
cur.next = node
cur = cur.next
cur.next = None
return dummy.next