Merge k Sorted Lists

Naive Solution

One straightforward approach is to collect all the values from the linked lists into a single array, sort the array, and then construct a new linked list from the sorted array.

Algorithm

1. Iterate through each linked list in the input array.
2. Extract all the values from each linked list and append them to a single array.
3. Sort the array.
4. Create a new linked list from the sorted array.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    values = []
    for linked_list in lists:
        current = linked_list
        while current:
            values.append(current.val)
            current = current.next
    
    values.sort()

    if not values:
        return None

    head = ListNode(values[0])
    current = head
    for i in range(1, len(values)):
        current.next = ListNode(values[i])
        current = current.next
    
    return head

Time Complexity

• O(N log N), where N is the total number of nodes in all linked lists. This is due to the sorting step.

Space Complexity

• O(N), where N is the total number of nodes in all linked lists, as we store all values in an array.

Optimal Solution: Priority Queue (Min-Heap)

A more efficient approach utilizes a priority queue (min-heap) to keep track of the smallest node among all linked lists. This avoids sorting the entire array at once and allows us to build the merged list in a sorted manner.

Algorithm

1. Create a min-heap.
2. Insert the head of each linked list into the min-heap.
3. While the min-heap is not empty:
   • Extract the node with the smallest value from the min-heap.
   • Append this node to the merged list.
   • If the extracted node has a next node, insert the next node into the min-heap.

Code

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, node))

    dummy = ListNode()
    current = dummy

    while heap:
        val, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))

    return dummy.next

Time Complexity

• O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes O(log k) time, and we perform these operations for each of the N nodes.

Space Complexity

• O(k), where k is the number of linked lists. This is the space used by the min-heap.

Edge Cases

• Empty input list: If the input lists is empty, return None.
• Empty linked lists: If any of the linked lists are empty, they should be handled gracefully. The priority queue approach handles this automatically.
• All empty linked lists: If all linked lists are empty, the result should be an empty linked list (i.e., None).