Linked List Random Node

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?

这道题如果不考虑follow up会很简单，遍历一遍链表，把值存到一个List里，取的时候随机出一个下标来取就好。

public class Solution {

    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    private ArrayList<Integer> a=new ArrayList<Integer>(); 
    private int b = 0;
    public Solution(ListNode head) {
        while (head!=null) {
            a.add(head.val);
            head = head.next;
            b++;
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int index = (int)(Math.random()*(b));
        int res = a.get(index);
        return res;
    }
}

但是，如果在长度未知的情况下进行随机，这个就不行了，比如链表是随时变化的，就不能用这样的方法。
这是著名的蓄水池问题，在未知长度的数据中随机出k个数据。
比如，我们要从1，2，3中随机选出一个。
假设我们的结果是res
我们从头开始遍历这个链表：
遍历到第一个时，我们选1的概率是1，res=1
遍历到第二个时，我们选2的概率应该是1/2，1的概率也应该是是1/2。我们以1/2的概率执行res＝2
遍历到第三个时，我们选每个数的概率是1/3，我们以1/3的概率执行res＝3
此时，res＝1，2，3的概率分别是1/2(1-1/3),1/2(1-1/3),1/3。即1/3，1/3，1/3
所以：

public class Solution {
    ListNode head;
    Random random;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int count = 0;
        int result = -1;
        ListNode dummyhead = head;
        while(dummyhead != null) {
            if(random.nextInt(++count) == 0) {
                result = dummyhead.val;
            }
            dummyhead = dummyhead.next;
        }
        return result;
    }
}

Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Note:The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

这个和上面的问题几乎一样的，就是这次选的时候只在特定的值中选

public class Solution {
    int [] data;
    Random random;
    public Solution(int[] nums) {
        data = nums;
        random = new Random();
    }
    
    public int pick(int target) {
        int count = 0;
        int result = -1;
        for(int i = 0;i<data.length;i++) {
            if (data[i]==target) {
                 if(random.nextInt(++count) == 0) {
                    result = i;
                }
            }
        }
        return result;
    }
}