23. Merge k Sorted Lists

 You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.




    Merging k sorted linked lists into a single sorted linked list is a common operation in computer science. This can be useful, for example, when we have a large number of sorted lists that need to be combined into a single list for further processing.

    One way to solve this problem is to use a recursive approach. We can start by merging the first two lists into a new list, then merge the resulting list with the third list, and so on, until all the lists have been merged into a single list. This approach has a time complexity of O(nk log k), where n is the total number of elements in all the input lists and k is the number of input lists. This is because we need to merge each pair of lists in O(n) time, and we need to do this log k times (since we are repeatedly dividing the number of lists in half).

    Another approach is to use a priority queue to keep track of the smallest element in each of the input lists. We can then repeatedly extract the smallest element from the priority queue and append it to the resulting list, until all the elements from all the input lists have been added to the resulting list. This approach has a time complexity of O(n log k), since we need to insert and extract elements from the priority queue in log k time, and we need to do this for each of the n elements in the input lists.

Here is an example of using this second approach to solve the problem:

from heapq import heapify, heappop, heappush
from typing import List, Union

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

def merge_k_lists(lists: List[ListNode]) -> Union[ListNode, None]:
    if not lists:
        return None

    # Create a priority queue with the first node of each list
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapify(heap)

    # Create a new head node
    head = ListNode(0)
    curr = head

    # Loop through the priority queue, adding the smallest node to the new list
    while heap:
        val, i, node = heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heappush(heap, (node.next.val, i, node.next))

    # Return the head of the new list
    return head.next



This function takes a list of linked lists as input and returns a single linked list that contains all the elements of the input lists in ascending order. It first creates a priority queue with the first node of each input list, using the value of the node as the key. It then creates a new head node and begins looping through the priority queue. For each iteration, it extracts the smallest element from the queue, adds it to the new list, and adds the next node in the list associated with the extracted element to the queue (if there is a next node). This process continues until the queue is empty, at which point all the elements from the input lists have been added to the new list and the function returns the head of the new list.

Hope it shall solver your query .!!