Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लिंक्ड सूची को समतल करना


इस समस्या में, हमें दो पॉइंटर नोड्स, राइट और डाउन से युक्त एक लिंक्ड सूची दी गई है।

  • राइट नोड मुख्य लिंक्ड सूची पॉइंटर है।

  • डाउन नोड उस नोड से शुरू होने वाली द्वितीयक लिंक्ड सूची के लिए है।

सभी लिंक्ड सूचियाँ सॉर्टेड हैं।

हमारा कार्य एक प्रोग्राम बनाना है जो लिंक्ड सूची को समतल करे और परिणामी सूची स्वयं सॉर्टेड होगी।

समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट

C++ में लिंक्ड सूची को समतल करना

आउटपुट

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

  1. 2D मैट्रिक्स से लिंक्ड लिस्ट बनाएं C++ में (पुनरावर्ती दृष्टिकोण) 2D मैट्रिक्स से लिंक्ड लिस्ट बनाएं C++ में (पुनरावर्ती दृष्टिकोण)

    मान लीजिए हमारे पास एक मैट्रिक्स है, हमें इसे पुनरावर्ती दृष्टिकोण का उपयोग करके 2D लिंक्ड लिस्ट में बदलना है। इस लिस्ट में राइट (दायां) और डाउन (नीचे) पॉइंटर होंगे। उदाहरण के लिए, यदि इनपुट इस तरह का है: 10 20 30 40 50 60 70 80 90 तो आउटपुट होगा: इसे हल करने के लिए, हम निम्न चरणों का पाल

  1. C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें

    हमें नोड्स के साथ एक सर्कुलर लिंक्ड लिस्ट दी गई है और कार्य सर्कुलर लिंक्ड लिस्ट में मौजूद नोड्स की संख्या की गणना करना है। सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट का एक प्रकार है जिसमें पहला तत्व अंतिम तत्व की ओर इंगित करता है और अंतिम तत्व पहले तत्व की ओर इंगित करता है। सिंगली लिंक्ड लिस्ट और डबली लिं

  1. C++ में बाइनरी ट्री में लिंक्ड लिस्ट C++ में बाइनरी ट्री में लिंक्ड लिस्ट

    मान लीजिए हमारे पास एक बाइनरी ट्री रूट और एक लिंक्ड लिस्ट है जिसका हेड पहला नोड है। हमें True लौटाना है अगर लिंक्ड लिस्ट में हेड से शुरू होने वाले सभी एलिमेंट्स बाइनरी ट्री में किसी डाउनवर्ड पथ से मेल खाते हैं, अन्यथा False। उदाहरण के लिए, अगर ट्री है: और लिंक्ड लिस्ट [1,4,2,6] है, तो आउटपुट true