Merge K Sorted Lists

Problem Statement:

In this statement we have a List of Linked Lists where each and every linked list is sorted in ascending order, You need to merge the linked lists in such a way that the obtained list should be in non-decreasing order (ascending order)

Sample Test Cases:

Note: Before getting into the article, try coming up with an approach first for having better understanding.

Method 1: Brute Force Approach

A straightforward approach involves initializing the result with the first list and then iterating through the remaining lists. For each node in the current list, insert it into the result in a sorted manner.

Below is the Java Implementation of the above mentioned approach

Output:

Complexity Analysis:

Time complexity: O(n^k-1), because we are traversing n times on each of the K lists.

Space Complexity: O(1).

Method 2: Using Min Heap:

This solution employs the Min Heap approach. Initially, a Min Heap is constructed by inserting the first element from each of the K Linked Lists. The algorithm proceeds by extracting the root element from the Min Heap and appending it to the output Linked List. Subsequently, the next element from the Linked List associated with the extracted element is inserted into the Min Heap. This process iterates until there are no elements remaining in the Min Heap, ultimately yielding the desired result.

Algorithm:

1. Create a Min Heap to store elements from the K linked lists along with their list index.
2. Insert the first element from each linked list into the Min Heap with its list index.
3. Initialize an empty result linked list.
4. Repeat the following steps until the Min Heap is not empty:
   • Extract the root element from the Min Heap, which contains the minimum value along with its list index.
   • Append the extracted element to the result linked list.
   • If there is a next element in the linked list associated with the extracted element, insert that element into the Min Heap with its list index.
5. Return the head of the result linked list.

Note: The Min Heap ensures that the smallest element among the remaining candidates is always at the root, facilitating the construction of the sorted merged list. The algorithm terminates when there are no more elements in the Min Heap, indicating that all linked lists have been processed.

Java Implementation of the above mentioned approach

Explanation:

Output:

Complexity Analysis:

Time Complexity: O(n*k*logk)

Space Complexity: O(k)

Method 3: Using Divide & Conquer Approach:

The approach involves iteratively pairing up sorted lists, halving the total number of lists at each iteration, until all the lists are merged.

Follow these steps to solve the problem:

1. Combine K lists by merging each pair efficiently with linear time complexity and utilizing O(N) space.
2. After the initial cycle, there will be K/2 lists, each with a size of 2N. Subsequently, in the second cycle, there will be K/4 lists, each with a size of 4N, and so forth.
3. Continue this process iteratively until only one list remains.

Java implementation of the above mentioned approach

Output:

Complexity Analysis:

Time Complexity: O(n*k^2)

Space Complexity: O(n)