# 382 Linked List Random Node

給一linked list，回傳隨機一個node的值，並保證每個node都有相同的機率被選到。

Idea 這題還是看答案+畫樹狀圖才看懂

舉最簡單的例子，假如linked list是 1->2->3 讀到1時，選到1的機率是1，讀到2時，有1/2機率是1，1/2機率是2，讀到3時，選到1,2,3的機率都是1/3。

此結果只要每次讀到第n個node，就以1/n的機率把原本選的數字換掉就可以達到。原因如樹狀圖所示：

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
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) {
        random = new Random();
        this.head = head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode c = head;
        int r = c.val;
        for(int i=1;c.next != null;i++){

            c = c.next;
            if(random.nextInt(i + 1) == i) r = c.val;                        
        }

        return r;
    }
}

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

ref: https://leetcode.com/problems/linked-list-random-node/discuss/85662/Java-Solution-with-cases-explain

這題的延伸問題是：random取k個數字，參考連結 https://www.geeksforgeeks.org/reservoir-sampling/ 和樹狀圖