382. Linked List Random Node

主要就是后FOLLOW UP,如何在不知道总数的情况下，随机选取。

用的是沼气池理论，貌似是统计那块的。

if (rdm.nextInt(base) == 0) res = temp.val;

这行的意思是，还是遍历，但是对于某个节点，被选到的几率是1/x,比如第四个，被选中的概率是1/4，但是我们此时不停止遍历，继续遍历，如果以后选中别的，刚才被选中的第四个会被覆盖，所以为了保证第4个被选中，后面必须不被选中，那概率就是:
1/4 * 4/5 * 5/6 ... n-1/n

对于某一个点X，不被选中的概率是x-1/x。

最后乘下来正好是1/n

public class Solution {

    ListNode head;
    /** @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;
    }
    
    /** Returns a random node's value. */
    public int getRandom() 
    {
        Random rdm = new Random();
        
        int res = -1;
        
        // 1/4 * 4/5 * 5/6... n-1/n
        ListNode temp = head;
        for (int base = 1; temp != null; base++, temp = temp.next) 
        {
            if (rdm.nextInt(base) == 0) res = temp.val;
        }
            
        return res;
    }
}