题目描述

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

样例

// Init a singly linked list [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() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-random-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(蓄水池抽样) $O(n)$

感觉是个ds的常考题 在网易考拉面过 在一些别的面经里也见过

池子一共n个元素，抽样m个每个都是以相同的概率概率($\frac{m}{n}$)被选择，这题$m=1$.
步骤：扫描链表
1. 当已经选择的个数少于m的时候直接按顺序放入
2. 当扫到第$k$个数，$k>m$，生成随机整数$k$。当$k$满足 R%k $\in [0,m-1]$ 用第$k$个数替换已经选择的第R%k位置的数
3. 重复知道扫完整个列表

证明：
当$k \leq m$ 的时候 被选择元素$(s_1 .... s_m)$被选择的概率是1
当$k > m$ 的时候，元素$s_k$被选择的概率是$\frac{m}{k}$
当$k >m $，$i <m$， $s_i$被$s_k$ 替换的概率是$1/m$，

此时$k$最小是$m+1$

第$m+1$次操作是我们用$\frac{m}{m+1}$的概率选出$s_{m+1}$并用$\frac{1}{m}$的概率替换任意$s_i$满足$i<m$. 那$s_i$在$m+1$次操作之后 没有被$s_{m+1}$ 替换的概率是 $ 1-\frac{1}{m} \cdot \frac{m}{m+1} = \frac{m}{m+1}$ (注意这个概率， 每次新插入和未被替换的概率相等)

同理 第$m+2$次操作 $s_i$没有被$s_{m+2}$ 替换的概率是 $1-\frac{1}{m} \cdot \frac{m}\{m+2} = \frac{m+1}{m+2}$
.
.
.
第$n$次操作 $s_i$没有被$s_n$ 替换的概率是 $1- \frac{1}{m} \cdot \frac{m}{n} = \frac{n-1}{n}$

因为每次操作独立， 经过总共n次操作 $\forall i, s_i$ 被保留的概率是 $1^m \cdot \frac{m}{m+1} .....\frac{n-1}{n} = \frac{m}{n}$

C++ 代码

class Solution {
private:
    ListNode * dummy;
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) {
        dummy = new ListNode(-1);
        dummy->next = head;

    }

    /** Returns a random node's value. */
    int getRandom() {
        auto tail = dummy->next;
        int ans=0;
        for(int i =1; tail; i++){
            if(rand() %i +1 ==1) ans = tail->val;
            tail = tail->next;
        }

        return ans;
    }
};