LeetCode #23: Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/

To solve this problem, we can use a min heap to keep track of the minimum element from each list. We can then pop the minimum element and add it to our result linked list. We can continue this process until all elements have been added to our result linked list.

Here are the steps to solve this problem:

1. Edge case: If the input list is empty, return None.
2. Initialize a min heap with the first element of each list. We can use Python’s heapq module to implement the min heap. We will add the first element of each list to the heap and continue adding elements until there are no more nodes in any of the lists.
3. Initialize a dummy head and a current node for the merged list.
4. While the heap is not empty, pop the minimum element from the heap.
5. Add the minimum element to the next element of the current node.
6. Update the current node to be the newly added element.
7. If there are more elements in the list that the current node belongs to, add the next element of that list to the heap.
8. Return the next element of the dummy head (which is the head of the merged list).

Here is the implementation of the above steps in Python:

import heapq

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # Edge case: If the input list is empty, return None
        if not lists:
            return None
        
        # Initialize the min heap with the first element of each list
        heap = []
        for node in lists:
            temp = node
            while temp:
                heapq.heappush(heap, temp.val)
                temp = temp.next
        
        # Initialize the dummy head and current node
        dummy = curr = ListNode()
        
        # While the heap is not empty
        while heap:
            # Pop the minimum element from the heap
            val = heapq.heappop(heap)
            # Update the next element of the current node
            curr.next = ListNode(val)
            curr = curr.next
            if curr.next:
                heapq.heappush(heap, curr.next.val)
        
        # Return the next element of the dummy head (which is the head of the merged list)
        return dummy.next

The time complexity of this algorithm is O(n log k), where n is the total number of nodes in all k lists. This is because we are adding and removing elements to/from a min heap, which has a logarithmic time complexity for these operations. We do this n times, since there are n total elements in all k lists.

The space complexity of this algorithm is O(k), where k is the number of lists. This is because we are storing the first element of each list in the min heap. The total number of elements in the heap will never exceed k, since we are only adding one element to the heap for each list.