इस समस्या में, हमें दो पॉइंटर नोड्स वाली लिंक्ड लिस्ट दी जाती है, दाएं और नीचे।
-
दायां नोड मुख्य लिंक्ड सूची सूचक है।
-
डाउन नोड उस नोड से शुरू होने वाली सेकेंडरी लिंक्ड लिस्ट के लिए है।
सभी लिंक की गई सूचियां क्रमबद्ध हैं।
हमारा काम एक लिंक की गई सूची को समतल करने के लिए एक प्रोग्राम बनाना है और परिणामी सूची स्वयं एक क्रमबद्ध होगी।
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट
आउटपुट
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
समाधान दृष्टिकोण
समस्या का समाधान लिंक की गई सूची के लिए मर्ज सॉर्ट करना . का उपयोग करना है . यह विधि एक चपटी सूची बनाने के लिए सूचियों को क्रमबद्ध क्रम में पुनरावर्ती रूप से मर्ज करेगी।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
if (a == NULL)
return b;
if (b == NULL)
return a;
Node* result;
if (a->data < b->data){
result = a;
result->down = mergeList(a->down, b);
}
else{
result = b;
result->down = mergeList(a, b->down);
}
result->right = NULL;
return result;
}
Node* flattenLinkedList(Node* root){
if (root == NULL || root->right == NULL)
return root;
root->right = flattenLinkedList(root->right);
root = mergeList(root, root->right);
return root;
}
Node* push(Node* head_ref, int data){
Node* new_node = new Node();
new_node->data = data;
new_node->right = NULL;
new_node->down = head_ref;
head_ref = new_node;
return head_ref;
}
int main(){
head = push(head, 7);
head = push(head, 1);
head->right = push(head->right, 11);
head->right = push(head->right, 5);
head->right = push(head->right, 4);
head->right->right = push(head->right->right, 12);
head->right->right = push(head->right->right, 6);
head->right->right->right = push(head->right->right->right, 8);
head->right->right->right->right = push(head->right->right->right->right, 16);
head = flattenLinkedList(head);
cout<<"The Flattened Linked list is : \n";
Node* temp = head;
while (temp != NULL){
cout<<temp->data<<" => ";
temp = temp->down;
}
cout<<"NULL";
return 0;
} आउटपुट
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL