Linked List: Sort a “k”sorted Doubly Linked list

Problem Statement:

You are given a DLL and each node is at most ‘k’ away from its target position.
You need to sort the DLL

Example

Example: 3 <-> 6 <-> 2 <-> 12 <-> 56 <-> 8 

k = 2

Output:
2 <-> 3 <-> 6 <-> 8 <-> 12 <-> 56 

Solution

You need to create a Min Heap of first (k+1) elements from the input DLL

Then one by one remove the min element from heap and put in the resultant LL

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 

struct compare 
{
    bool operator()(struct Node* p1, struct Node* p2)
    {
        return p1->data > p2->data;
    }
};
 
struct Node* sort_k_sorted_DLL(struct Node* head, int k)
{
    if (head == NULL)
        return head;
 
    //min heap
    priority_queue<Node*, vector<Node*>, compare> pq;
 
    struct Node* newHead = NULL, *last;
 
    // create a Min Heap of first (k+1) elements from input DLL
    for (int i = 0; head != NULL && i <= k; i++) 
    {
        pq.push(head);
         head = head->next;
    }
 
    while (!pq.empty()) 
    {
 
        if (newHead == NULL) 
        {
            newHead = pq.top();
            newHead->prev = NULL;
 
            last = newHead;
        }
 
        else 
        {
            last->next = pq.top();
            pq.top()->prev = last;
            last = pq.top();
        }
 
        pq.pop();
 
        if (head != NULL) 
        {
            pq.push(head);
 
            head = head->next;
        }
    }
 
    last->next = NULL;
 
    return newHead;
}
 
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = 
          (struct Node*)malloc(sizeof(struct Node));
     new_node->data = new_data;
 

    new_node->prev = NULL;
 
    new_node->next = (*head_ref);
 
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    (*head_ref) = new_node;
}

void printList(Node* head) 
{ 
    while (head != NULL) { 
        cout << head->data << " "; 
        head = head->next; 
    } 
} 
 
int main()
{
    struct Node* head = NULL;
 
    push(&head, 8);
    push(&head, 56);
    push(&head, 12);
    push(&head, 2);
    push(&head, 6);
    push(&head, 3);
 
    int k = 2;
  
    cout << "Original Doubly linked list: ";
    printList(head);
 
    head = sort_k_sorted_DLL(head, k);
 
    cout << "\nDoubly linked list after sorting: ";
    printList(head);
 
    return 0;
} 

Output:

Original Doubly linked list: 3 6 2 12 56 8
Doubly linked list after sorting: 2 3 6 8 12 56

 

 

 

 

 

 

Write a Comment

Leave a Comment

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