Merge k sorted linked lists | Set 2 (Using Min Heap)

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

In this problem, we will be given K sorted linked lists. We need to merge all the lists such that the newly created list is also in sorted order.

Problem Statement Understanding

The problem statement is quite straightforward, we will be given K sorted linked lists, and then we need to form a linked list using the nodes of all the given linked lists such that the newly formed list is sorted in order.

Let's try to understand the problem with the help of examples:
If the sorted lists given to us are:

  • According to the problem statement, we need to merge all these given linked lists into a single linked list in such a way that after merging, the final linked list is sorted in nature.
  • The list that we need to return must contain all the nodes of all three given lists in sorted order.
  • So, after merging the newly formed sorted list will be:

Let’s take another example:
If the sorted lists given to us be 2→8→9→10→NULL, 11→13→17→NULL.

  • In this case, after merging, the final resultant sorted linked list will be 2→8→9→10→11→13→17→NULL.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

In this approach, we will be using min heap.

  • First, we need to create a min-heap.
  • Since the smallest elements are present at the beginning of each list as each of them is sorted, so, we need to insert each list’s first element in our heap.
  • Now, while our heap is not empty, we need to take out its top element and attach it at the end of our result list.
  • The node which we attached to the end of the result list will be from one of the K given linked list, so if the next node of the node which we attached at the end of the result list exists, we need to push it into the min heap.
  • Finally, when our min heap is empty, at that time the result list will contain all the nodes of the K given linked list in sorted order.

Algorithm

  • Write a comparator function for the priority queue to store minimum elements at the top.
  • Push starting node of all the lists in the min-heap.
  • Now, create a node head with zero value that will act as a dummy node for our newly created list.
  • Initialize a temp variable with the address of the above-created node.
  • Run a while loop till the priority queue size is greater than 0.
  • Store the topmost element of the queue into a variable, say p.
  • Now remove the top element from the priority queue.
  • Attach the node p at the end of our new list by doing temp->next = p.
  • Now advance the temp variable by one node i.e, temp = temp->next.
  • If the node after p is not NULL, push the node after p into the priority queue.
  • After the completion of the while loop, return head->next, as it will be the first node of our newly created linked list.

Dry Run




Code Implementation

#include
using namespace std;

// class with constructor for a node of Linked list
class Node {
    public:
    int data;
    Node* next;
    // constructor
    Node(int x){
        data = x;
        next = NULL;
}
};
// This function prints data of the linked list
void print(Node* head)
{
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}

// this is the comparator function for the priority queue to
// make it behave as a min-heap
struct compare
{
    bool operator()(Node* &a,Node* &b)
    {
        return a->data>b->data;
    }
};

// This function merges 'K' sorted lists into one sorted list
Node* mergeKLists(Node* arr[], int back)
{
    priority_queue,compare>minh;
    for(int i=0;i<=back;i++)
    {
        if(arr[i]!=NULL) minh.push(arr[i]);
    }
    Node* head=new Node(0);
    Node* temp=head;
    while(minh.size()>0)
    {
        Node* p = minh.top();
        minh.pop();
        temp->next = p;
        temp=temp->next;
        if(p->next!=NULL) minh.push(p->next);
    }
    return head->next;
}

// main function
int main()
{
    Node * arr[3];
    Node *head = new Node(2);
    head->next = new Node(3);
    head->next->next = new Node(5);
    Node *h2 = new Node(1);
    h2->next = new Node(4);
    h2->next->next = new Node(8);

    Node *h3 = new Node(6);
    h3->next = new Node(7);
    h3->next->next = new Node(9);

    arr[0] = head;
    arr[1] = h2;
    arr[2] = h3;
    
    cout<<"Final resultant merged linked list"<

						 

Output

Final resultant merged linked list
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL

Time Complexity: O(NKlog(K)), N is the number of nodes in the list, and K is the total number of lists.

So, in this blog, we have tried to explain how you can merge K sorted linked lists using a min-heap. If you want to practice more questions on linked lists, feel free to solve them at Prepbytes Linked List.

Previous post Length of longest palindrome list in a linked list using O(1) extra space
Next post Merge K sorted linked lists | Set 1

Leave a Reply

Your email address will not be published. Required fields are marked *