# Java two solutions, easy to understand

• The first solution is the trivial one,

we just count the length of the list, and then return a random number "r" between 0 and length,

then we traverse the list again and stop at"r" steps and then return the value of that ListNode.

``````public class Solution {

Note that the head is guaranteed to be not null, so it contains at least one node. */
int count = 0;
while(tem != null) {
count++;
tem = tem.next;
}
}

/** Returns a random node's value. */
public int getRandom() {
Random r = new Random();
int random = r.nextInt(count);
for (int i = 0; i < random; i++) {
}
}
}
``````

Another one only traverse the list once, and we don't need to know the length of the list.

``````public class Solution {

Note that the head is guaranteed to be not null, so it contains at least one node. */
Random random;
random = new Random();
}

/** Returns a random node's value. */
public int getRandom() {
int count = 0;
int result = -1;
if(random.nextInt(++count) == 0) {
}
}
return result;
}
}
``````

prof: for example: we have 3 numbers : 1,2,3.
step 1: we pick 1 probability 1/1 .
step 2: we have 1/2 probability to pick 2, so there are 1/2 chance we return 1 and 1/2 chance return 2.
step 3: we have 1/3 probability to pick 3, and the probability that we return 2 is that we pick 2 in step 2 and don't pick 3 and step 3, so the probability of returning 2 is 1/2 * (1- 1/3) = 1/3. so in step 3 we have 1/3 chance to return 1, 1/3 chance to return 2, and 1/3 chance to return 3.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.