# 0382. Linked List Random Node
###### tags: `Leetcode` `Medium` `Reservoir Sampling`
Link: https://leetcode.com/problems/linked-list-random-node/
## 思路
Reservoir Sampling
## Code

class Solution {
    private ListNode head;
    private ListNode curr;
    Random rand;
    public Solution(ListNode head) {
        this.head = head;    
        this.curr = head;
        rand = new Random();
    }
    
    public int getRandom() {
        this.curr = head;
        int cnt = 0;
        int idx = 0;
        
        while(curr != null){
            cnt++;
            if(rand.nextInt(cnt)==0){
                idx = curr.val;
            }
            curr = curr.next;
        }
        return idx;
    }
}