【Leetcode-每日一题】链表随机节点

【Leetcode-每日一题】链表随机节点

链表随机节点
难度：中等

将链表转化为数组，通过随机函数得到下标，返回该下标的值即可。
代码如下：

	
class Solution {
    List list = new ArrayList<>();
    Random random = new Random();
    public Solution(ListNode head) {
        while(head !=null){
            list.add(head.val);
            head = head.next;
        }
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

执行结果：成功

完成后看了下题解，都提到了蓄水池法，之前没有听说过，所以也记录学习一下。

对于今天这道题，它的处理过程如下：

只需要记录链表头节点；
从头开始遍历，同时声明一个变量记录选取到的元素，对于遍历到的第 i 个节点，生成一个 [0, i) 的随机数，如果这个随机数等于 0，则把当前值赋值给上述变量；
遍历完链表上述变量中保存的就是我们返回的值。
水塘抽样，适用于非常大的数据量，一般是流式的数据，你不知道大小有多少个，随机选取多个元素，这些被选取的元素放在一个池子中，随时有可能返回这个池子中的数。比如，在大数据领域，数据一直在处理，但是，在某个时间节点需要随机返回 5 个已经处理过的数据，我们就可以声明一个大小为 5 的池子来处理。

当然，今天这道题只需要返回一个随机元素，也可以使用水塘抽样来处理，只是有点大材小用了。
正确性证明： 遍历到第 i 个元素时被选中的概率是 1/i，且在之后的遍历中不被替换，我们用 P(i) 表示第 i 个元素被选中的概率，!P(i) 表示第 i 个元素不被选中的概率，所以有： P(i) * !P(i + 1) * … * !P(n) = 1/i * (1 - 1/(i+1)) * … * (1 - 1/n) = 1/i * i/(i+1) * … * (n-1)/n = 1/n ，所以，每个元素返回的概率都是 1/n。
代码如下：

class Solution {

    ListNode head;
    public Solution(ListNode head) {
        this.head = head;
    }
    
    public int getRandom() {
        int i = 0;
        int pool = 0;
        ListNode cur = head;
        while (cur != null) {
            i++;
            int rand = (int) (Math.random() * i);
            if (rand == 0) {
                pool = cur.val;
            }
            cur = cur.next;
        }
        return pool;
    }
}