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();

Tips:

Reservoir sampling

水塘抽样

由于限定了head一定存在，所以我们先让返回值res等于head的节点值，然后让cur指向head的下一个节点，定义一个变量i，初始化为1，若cur不为空我们开始循环，我们在[0, i]中取一个随机数，如果取出来0，那么我们更新res为当前的cur的节点值，然后此时i自增一，cur指向其下一个位置，这里其实相当于我们维护了一个大小为1的水塘，然后我们随机数生成为0的话，我们交换水塘中的值和当前遍历到底值，这样可以保证每个数字的概率相等

Suppose we see a sequence of items, one at a time. We want to keep a single item in memory, and we want it to be selected at random from the sequence.

If we know the total number of items (n), then the solution is easy: select an index i between 1 and n with equal probability, and keep the i-th element.

The problem is that we do not always know n in advance. A possible solution is the following:

* Keep the first item in memory.
* When the i-th item arrives (for i>1):
* with probability 1/i, keep the new item instead of the current item; or equivalently
* with probability 1-1/i, keep the current item and discard the new item.

So:

* when there is only one item, it is kept with probability 1;
* when there are 2 items, each of them is kept with probability 1/2;
* when there are 3 items, the third item is kept with probability 1/3,
  and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
* by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

import java.util.Random;

public 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) {
        this.head = head;
        random = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode result = head;
        ListNode cur = head;
        int size = 1;
        while (cur != null) {
            if (random.nextInt(size) == 0) {
                result = cur;
            }
            size++;
            cur = cur.next;
        }
        return result.val;
    }
}

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