import java.util.*;
public class Solution {
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
ListNode head = null;
Random randomGenerator = null;
public Solution(ListNode head) {
this.head = head;
this.randomGenerator = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
ListNode result = null;
ListNode current = head;
for(int n = 1; current!=null; n++) {
if (randomGenerator.nextInt(n) == 0) {
result = current;
}
current = current.next;
}
return result.val;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
O(n) Time & O(1) Space Java Solution



@lixx2100 Thank you.
and this is my c++ solution rewrite from abi93k's solutionclass Solution { ListNode* flag; public: /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */ Solution(ListNode* head) { flag = head; } /** Returns a random node's value. */ int getRandom() { ListNode* node = flag; int ret = node>val; for(int i = 1; node; ++i) { if(rand() % i == 0) ret = node>val; node = node>next; } return ret; } }; /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

The probability would be equal.
This is the basic concept like Knuth's shuffle.I just do not know what "its length is unknown to you"  don't we get the length once we traverse it, and a second getRandom() call would have the length known?
Maybe it is easier to paraphrase like "its length may be varying". In this way the fixedlength solution (using extra space) won't work well any more.

@GOPCBR nextInt(n) chooses a random value which lies between 0 and n1. In the first iteration, randomGenerator.nextInt(1) will return 0. Always.


@jtimberlakers it looks like the probability of choosing 1st element is: 1/1 * (21)/2 * (31)/3 * (41)/4 * ... (N1)/N = 1/N. And the probability of choosing ith element is 1 * 1/i * (i+1  1) / (i + 1) * ... (N1)/N = 1/N. So every element has equal probability of being chosen.
Side note: there are many subcases that will reach ith element, e.g., case 1: 1st element chosen, 2nd element not chosen, 3rd element chosen, 4th element not chosen; case 2: 1st element chosen, 2nd element chosen, 3rd element not chosen ...). No matter what, their sum is 1.

@dachuan.huang Thanks! Yes, when computing ith element's probability, we don't care whether one of the previous elements is chosen since we will set it to the result if it's chosen. So we can start from i, i is chosen and all elements after i are not chosen.

@sometimescrazy Cool! To take a step back, I am always curious about one question: how does one get this solution?
One way I can think of (after I know the solution..) is: we want equal probability in N elements, so let's make the probability as 1/N. The numerator is 1, and the denominator is N.
It turns out that the numerator can come from the element itself, and the denominator can come from the last element. Then the 1/1 * 1/2 * 2/3 * .. * (N1)/N method comes in mind..

@dachuanhuang As long as you know Reservoir_sampling or Knuth's shuffle, the solution comes naturally.
As to how these guys (e.g. Knuth) come up with the algorithm at the first place, well they are genius.

@mycoy No. The solution has nothing to do with node values. It is only working with "index": see "current = current.next".

Can someone expand @dachuanhuang explanation please? Maths and stats are not part of my day to day life so I'm struggling a bit to grasp his/her explanation.
I get what the Random algo does and how it works (ie you get a 'random' number between 0 and n  1)  so I would put it this way:
1st element > you have 1/1 chance of getting it
2nd element > 1/2
3rd element > 1/3
4rd element > 1/4
nth element > 1/nI failed to understand how he/she proved the odds are the same for all elements. Can someone clarify that to me please?

@claudineirdj so the probability of the event "the 1st element is chosen" is actually a combination of lots of events. When the 1st element is chosen, in the 1st round, we need to choose it (1/1 probability); in the 2nd round, we cannot overwrite the existing choice, how can we guarantee that we don't overwrite the existing choice? when the random integer is not 0. The probability of the event that the random integer is not 0 is: (21)/2.
The event "the 1st element is chosen" is A. Then P(A) = P(A1) * P(A2) *...*P(An) .
A1: the 1st element is chosen in the 1st round.
A2: the chosen element is not overwritten in the 2nd round.
so on ...So that's the idea. Just a chain of multiplication.

@abi93k This question did not say the list can be modified after creation, why not just cache its length and do nextInt() once and just get to the node. No need to iterate the whole list every time, i think.

If someone cannot understand, could try my explanation:
https://discuss.leetcode.com/topic/55049/javasolutionwithcasesexplain