【leetcode】382 链表随机节点（链表，蓄水池抽样）

题目链接：https://leetcode-cn.com/problems/linked-list-random-node/

题目描述

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

思路

该题是典型的蓄水池抽样算法，在流式到达的N个数中选择k个数，其中每个数被选择的概率相同。
（1）首先选择前k个数据
（2）for i = k+1 ~ n
对于第i个数据，以 k/i 的概率选择第i个数据，并且随机替换已选择的k个数据中的一个，此时i数据被选择的概率为k/i * 1/k = 1/i

代码

class Solution {
    ListNode *head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
        srand(time(NULL));
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        int i = 2;
        int ret = head->val;
        ListNode* p = head->next;
        while(p){
            if (rand() % i == 0)
                ret = p->val;
            i++;
            p = p->next;
        }
        return ret;
    }
};