इस समस्या में, हमें दो पॉइंटर नोड्स, राइट और डाउन से युक्त एक लिंक्ड सूची दी गई है।
राइट नोड मुख्य लिंक्ड सूची पॉइंटर है।
डाउन नोड उस नोड से शुरू होने वाली द्वितीयक लिंक्ड सूची के लिए है।
सभी लिंक्ड सूचियाँ सॉर्टेड हैं।
हमारा कार्य एक प्रोग्राम बनाना है जो लिंक्ड सूची को समतल करे और परिणामी सूची स्वयं सॉर्टेड होगी।
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट

आउटपुट
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<<"समतल लिंक्ड सूची है : \n"; Node* temp = head; while (temp != NULL){ cout<<temp->data<<" => "; temp = temp->down; } cout<<"NULL"; return 0; } आउटपुट
समतल लिंक्ड सूची है : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL