Naive Approach: Brute Force

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

Steps:

1. Iterate through all linked lists.
2. Collect the values from each linked list into an array.
3. Sort the array.
4. Create a new linked list from the sorted array.

Code (Python):

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 across all linked lists. This is dominated by the sorting step.

Space Complexity: O(N), to store all the values in an array.

Optimal Approach: Priority Queue (Min-Heap)

A more efficient approach involves using a priority queue (min-heap) to keep track of the smallest element among all the linked lists.

Steps:

1. Create a min-heap.
2. Insert the head nodes of all non-empty linked lists into the min-heap.
3. While the min-heap is not empty:
   • Extract the node with the smallest value from the min-heap.
   • Add this node to the merged linked list.
   • If the extracted node has a next node in its original linked list, insert the next node into the min-heap.

Code (Python):

import heapq

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

def mergeKLists(lists):
    heap = []
    for linked_list in lists:
        if linked_list:
            heapq.heappush(heap, (linked_list.val, linked_list))
    
    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 across all linked lists 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), which is the space required to store the head nodes of the linked lists in the priority queue.

Edge Cases

• Empty list of lists: lists = [] should return None.
• Empty list within lists: lists = [[]] should return None.
• Lists containing None: The code should handle None values gracefully and skip them.