Merge $k$ Sorted Lists

Solution 1: Merge One by One

• Complexity: $O(kN)$, extreme case is insertion-sort.

Solution 2: Compare One by One

• Similar to merge-two-sorted-lists, but finds the min_node in all $k$ lists.
• Complexity: $O(kN)$

curr = prehead = ListNode(0)
lists = [node for node in lists if node]
while lists:
    min_node = min(lists, key=lambda node: node.val)
    min_idx = lists.index(min_node)
    curr.next = min_node
    if not min_node.next:
        lists.pop(min_idx)
    else:
        lists[min_idx] = min_node.next
    curr = curr.next
return prehead.next

Solution 3: Min-Heap

class HeapNode:
    def __init__(self, node):
        self.node = node
 
    def __lt__(self, other):
        # Define comparison based on ListNode's value
        return self.node.val < other.node.val
 
 
def mergeKLists(lists):
    dummy = ListNode(0)
    current = dummy
    heap = []
 
    # Initialize the heap
    for l in lists:
        if l:
            heapq.heappush(heap, HeapNode(l))
 
    # Extract the minimum node and add its next node to the heap
    while heap:
        heap_node = heapq.heappop(heap)
        node = heap_node.node
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, HeapNode(node.next))
 
    return dummy.next