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

C++ में लिंक्ड लिस्ट रैंडम नोड


मान लीजिए हमारे पास एक सिंगली लिंक्ड सूची है, हमें लिंक्ड सूची से एक यादृच्छिक नोड का मान ढूंढना है। यहां प्रत्येक नोड के चुने जाने की समान संभावना होनी चाहिए।

उदाहरण के लिए, यदि सूची [1,2,3] है, तो यह 1, 2, और 3 की सीमा में यादृच्छिक नोड लौटा सकती है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • getRandom() विधि में, निम्नलिखित करें:
  • ret := -1, len := 1, v := x
  • जब तक v शून्य नहीं है
    • यदि rand() len से विभाज्य है, तो ret := v का मान
    • len को 1 से बढ़ाएं
    • v := v का अगला
  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; class ListNode{    public:    int val;    ListNode *next;    ListNode(int data){       val = data;       next = NULL;    } }; ListNode *make_list(vector<int> v){    ListNode *head = new ListNode(v[0]);    for(int i = 1; i<v.size(); i++){       ListNode *ptr = head;       while(ptr->next != NULL){          ptr = ptr->next;       }       ptr->next = new ListNode(v[i]);    }    return head; } class Solution {    public:    ListNode* x;    Solution(ListNode* head) {       srand(time(NULL));       x = head;    }    int getRandom() {       int ret = -1;       int len = 1;       ListNode* v = x;       while(v){          if(rand() % len == 0){             ret = v->val;          }          len++;          v = v->next;       }       return ret;    } }; main(){    vector<int> v = {1,7,4,9,2,5};    ListNode *head = make_list(v);    Solution ob(head);    cout << (ob.getRandom()); }

इनपुट

Initialize list with [1,7,4,9,2,5] Call getRandom() to get random nodes

आउटपुट

4 9 1

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

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

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

    इस समस्या में, हमें एक मल्टीलेवल लिंक्ड सूची दी गई है। हमारा कार्य मल्टीलेवल लिंक्ड सूची को समतल करने के लिए एक प्रोग्राम बनाना है। समतल करने का ऑपरेशन इस तरह से किया जाता है कि पहले स्तर के नोड्स पहले लिंक्ड सूची में आएंगे और फिर दूसरे स्तर के नोड्स आएंगे। मल्टीलेवल लिंक्ड सूची एक बहुआयामी डेटा संर

  1. - C++ प्रोग्राम: सर्कुलर सिंगली लिंक्ड लिस्ट कार्यान्वयन

    सर्कुलर सिंगली लिंक्ड लिस्ट अंतिम नोड पहले नोड (head) को इंगित करता है, जिससे एक वृत्त बनता है। केवल head संदर्भ से पूरी सूची एक्सेस की जा सकती है। C++ प्रोग्राम उदाहरण next; } while (ptr != head); } int main() { insert(3); insert(1); insert(7); insert(2); insert(9); c