Leetcode-382. random nodes of linked list

Mathematical problems - Random and sampling

---

Topic details

I'll give you a single linked list , Randomly select a node in the linked list , And return the corresponding node value . Every node The probability of being selected is the same .
Realization Solution class ：
Solution(ListNode head) Initializing objects with an array of integers .
int getRandom() Randomly select a node from the linked list and return the value of the node . All nodes in the linked list have the same probability of being selected .

---

Example ：

 Input 
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
 Output 
[null, 1, 3, 2, 2, 3]

 explain 
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); //  return  1
solution.getRandom(); //  return  3
solution.getRandom(); //  return  2
solution.getRandom(); //  return  2
solution.getRandom(); //  return  3
// getRandom()  Method should return randomly  1、2、3 One of them , The probability of each element being returned is equal .

Ideas :
Unlike arrays , Before traversing the linked list , We cannot know the total length of the linked list . Here we can use reservoir mining
sample ： Traverse the list once , After traversing to the m When a node , Yes 1/m The probability of selecting this node overrides the previous node selection .
Simple proof :

My code ：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution 
{
    
    ListNode* h;
public:
    Solution(ListNode* head) :h(head) {
    } // Use the header node with h Save it 
    
    int getRandom() 
    {
    
        int ans = h->val; // initialization ans Is the head node val
        ListNode* node = h->next; // utilize node Go back and forth 
        int i = 2;  // Because at this time node It's No 2 Nodes , therefore i Initialize to 2
        while (node) //  Traverse to the end 
        {
    
            // Randomly generate one [0,i) The random number , If it is 0,
            // Just change the answer to the number of nodes (1/i Probability )
            if ((rand() % i) == 0)
            ans = node->val;
            // Otherwise, continue to traverse the node backwards 
            ++i;
            node = node->next;
        }
        return ans;
    }
};

/** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */