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