LeetCode Algorithm 382. 链表随机节点

题目链接：382. 链表随机节点

算法：水塘抽样
数据结构：链表
思路：从链表头开始，遍历整个链表，对遍历到的第 i 个节点，随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将答案置为该节点值，否则答案不变。

水塘抽样算法证明：
P ( 第 i 个 节 点 的 值 成 为 最 后 被 返 回 的 值 ) = P ( 第 i 次 随 机 选 择 的 值 = 0 ) × P ( 第 i + 1 次 随 机 选 择 的 值 ≠ 0 ) × ⋯ × P ( 第 n 次 随 机 选 择 的 值 ≠ 0 ) = 1 i × ( 1 − 1 i + 1 ) × ⋯ × ( 1 − 1 n ) = 1 i × i i + 1 × ⋯ × n − 1 n = 1 n begin{array}{l} P( 第 i 个节点的值成为最后被返回的值) \ =P( 第 i 次随机选择的值 =0) times P( 第 i+1 次随机选择的值 neq 0) times cdots times P( 第 n 次随机选择的值 neq 0) \ =frac{1}{i} timesleft(1-frac{1}{i+1}right) times cdots timesleft(1-frac{1}{n}right) \ =frac{1}{i} times frac{i}{i+1} times cdots times frac{n-1}{n} \ =frac{1}{n} end{array} P(第i个节点的值成为最后被返回的值)=P(第i次随机选择的值=0)×P(第i+1次随机选择的值​=0)×⋯×P(第n次随机选择的值​=0)=i1​×(1−i+11​)×⋯×(1−n1​)=i1​×i+1i​×⋯×nn−1​=n1​​

class Solution {
    ListNode *head;
public:
    Solution(ListNode* head) {
        this->head = head;
    }
    
    int getRandom() {
        int i = 1, ans = 0;
        for (auto node = head; node; node = node->next) {
            if (rand() % i == 0) {
                ans = node->val;
            }
            ++i;
        }
        return ans;
    }
};