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