C++-এ লিংকড লিস্ট র‍্যান্ডম নোড

একটি সিঙ্গলি লিংকড লিস্ট দেওয়া আছে। লিস্ট থেকে একটি র‍্যান্ডম নোডের ভ্যালু ফেরত দিতে হবে। প্রতিটি নোডের নির্বাচন হওয়ার প্রোবাবিলিটি সমান হতে হবে। উদাহরণ: লিস্ট [1,2,3] হলে ১, ২, ৩-এর যেকোনো একটি র‍্যান্ডমলি ফেরত দেবে।

সমাধানের ধাপগুলো:

• getRandom() মেথডে নিচের কাজ করুন:
  • ret := -1, len := 1, v := x
  • v null না হওয়া পর্যন্ত:
    • যদি rand() % len == 0, ret := v->val
    • len++
    • v := v->next
  • 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