# Leetcode刷題學習筆記 -- Randomized
### [382. Linked List Random Node(Medium)](https://leetcode.com/problems/linked-list-random-node/)
給你一個singly linked list，每次都隨機從linked list中選一個element出來並且每個的機率都是一樣。

#### [水塘抽樣](https://zh.wikipedia.org/wiki/%E6%B0%B4%E5%A1%98%E6%8A%BD%E6%A8%A3)
這邊是用有名的水塘抽樣演算法，因為如果head的長度很長，或是根本不知道head的長度，就必須使用這個演算法。這個演算法的好處是不用先知道head的長度，也可以用公平的機率來抽取element。


1. 當node只有一個，抽到這個機率100%。所以default value設成第一個。
2. 當node有兩個，抽到機率各一半。所以

// 一半機率會選到第二個
if(rand() % 2 == 0)
    res = cur->val;

3. 當node有三個的時候，每個node都是1/3的機率會抽到。

// 1/3機率會選到第三個
if(rand() % 3 == 0)
    res = cur->val;

因為抽到第三個機率為1/3，所以抽到前兩個機率為2/3。而前兩個的機率為1/2，所以1/2 * 2/3 = 1/3。三個被抽到的機率都一樣。

class Solution {
    ListNode *h;
public:
    Solution(ListNode* head) {
        h = head;
    }
    int getRandom() {
        // 只有一個node
        if(!h->next) return h->val;
        // 兩個node以上
        int i = 2;
        int res = h->val;
        ListNode *cur = h->next;
        // 因為每個node被選到的機率都一樣
        // 意思是第一次選，每個node都有可能被選到
        // 所以每次呼叫getRandom都需要
        // 走訪全部的linked-list來確保每個node都會被選到
        while(cur) {
            // 選擇目前的node的機率為(1/i)
            if(rand() % i == 0) res = cur->val;
            // 選擇其他node的機率為((i - 1)/ i)
            i++;
            cur = cur->next;
        }   
        return res;
    }
};

###### tags: `leetcode` `刷題`