- to do
- linked-list-random-node
水塘抽样是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到主内存的情况。最常见例子为Jeffrey Vitter在其论文[1]
中所提及的算法R。
参照Dictionary of Algorithms and Data Structures[2]
所载的O(n)算法，包含以下步骤（假设阵列S以0开始标示）：
從S中抽取首k項放入「水塘」中對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0到j的整數r 若 r < k 則把水塘中的第r項換成S[j]項
class Solution {
private:
ListNode* head;
public:
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */ Solution(ListNode* head) {
this->head = head;
}
/** Returns a random node's value. */
int getRandom() {
int res = head->val;
ListNode* node = head->next;
int i = 2;
while(node){
int j = rand()%i;
if(j==0)
res = node->val;
i++;
node = node->next;
}
return res;
}
};
