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