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 {
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
int count = 0;
ListNode head;
public Solution(ListNode head) {
this.head = head;
ListNode tem = head;
while(tem != null) {
count++;
tem = tem.next;
}
}
/** Returns a random node's value. */
public int getRandom() {
ListNode fakehead = head;
Random r = new Random();
int random = r.nextInt(count);
for (int i = 0; i < random; i++) {
fakehead = fakehead.next;
}
return fakehead.val;
}
}
```

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

```
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. */
ListNode head;
Random random;
public Solution(ListNode head) {
this.head = head;
random = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
int count = 0;
int result = -1;
ListNode dummyhead = head;
while(dummyhead != null) {
if(random.nextInt(++count) == 0) {
result = dummyhead.val;
}
dummyhead = dummyhead.next;
}
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.