[数据结构与算法]学习总结：链表随机节点——（LC382）

题目：

给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字。

输入是一个单向链表，输出是一个数字，表示链表里其中一个节点的值。

思路：

1.

不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采
样：遍历一次链表，在遍历到第 m 个节点时，有 1/m 的概率选择这个节点覆盖掉之前的节点选择。

我们提供一个简单的，对于水库算法随机性的证明。对于长度为 n 的链表的第 m 个节点，最
后被采样的充要条件是它被选择，且之后的节点都没有被选择。这种情况发生的概率为

1/m×m/m+1×m+1/m+2× · · · × n?1/n=1/n（分母约掉）。因此每个点都有均等的概率被选择。

2.蓄水池抽样算法

最近经常能看到面经中出现在大数据流中的随机抽样问题

即：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。

当 k = 1 时，即此题的情况
也就是说，我们每次只能读一个数据。

假设数据流含有N个数，我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为 1/N

那如何保证呢？

先说方案：

每次只保留一个数，当遇到第 i 个数时，以 1/i的概率保留它，(i-1)/i的概率保留原来的数。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
 ListNode head;
 Random random;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
this.head = head;
this.random = new Random();//随机数
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
int reserve = 0;
ListNode cur = head;
int count = 0;
while(cur!=null){
count++;
int r = this.random.nextInt(count)+1;
if(r==count){
    reserve = cur.val;
}
cur  =cur.next;
}
return reserve;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */