382. Linked List Random Node

382. 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?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

My Solutions:

Iterate through the node from head with I = 1: if random nextInt(i) == 0, return the node's val as result

(Resorvior sampling: the probability to choose an element out of n elements is 1/n)

i从1开始代表总共iterate了几个数字，每个数字出现的几率是1/i，也就是r.nextInt(i) == 0的几率

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 ListNode head;
    
    public Solution(ListNode head) {
        this.head = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        
        Random r = new Random();
        ListNode n = head;
        int res = n.val;
        for (int i = 1; n != null; i++) {
            if (r.nextInt(i) == 0) res = n.val;
            n = n.next;
        }
        return res;
        
    }
}