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