Linked List Random Node

lc 382

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.

看randompick index 解释

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. */
    Random ran;
    ListNode head;
    public Solution(ListNode head) {
        this.ran = new Random();
        this.head = head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int count = 0;
        ListNode cur = head;
        int res = 0;
        while(cur != null){
            if(ran.nextInt(++count) == 0){
                res = cur.val;

            }
            cur = cur.next;
        }
        return res;
    }
}