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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• getRandom() विधि में, निम्न कार्य करें -

• रिट:=-1, लेन:=1, वी:=एक्स

• जबकि v शून्य नहीं है

  • यदि रैंड () लेन से विभाज्य है, तो रिट :=v का मान

  • लेन को 1 से बढ़ाएं

  • v :=v के आगे

• वापसी रिट

उदाहरण(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