# 382. Linked List Random Node

[Link](https://leetcode.com/problems/linked-list-random-node/)

**Solution**

這題必須確保每個node值出現的機率相等。

所以 只有一個node就是 100%出現\
&#x20;        有2個node就是 1/2出現\
&#x20;        有3個node就是 1/3出現\
\
假設有n個node，只要確保第n個node出現的機率是1/n，然後n-1個node出現的機率就是\
n-1 node在上一輪出線的機率 \* n node在最後一輪沒出線的機率1/n-1 \* n-1/n = 1/n。 \
以此類推第一個node出現的機率 =  1/2 \* 2/3 \* .....\*n-1/n = 1/n。

```
Random random;
    ListNode h;
    public Solution(ListNode head) {
        random = new Random();
        h = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode r = h;
        int v = r.val;
        
        for(int i = 1; r.next != null; i++){
            r = r.next;
            if(i == random.nextInt(i+1)) v = r.val;
        }
        return v;
    }
```
