```
class Solution {
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* h) {
head = h;
}
/** Returns a random node's value. */
int getRandom() {
ListNode* cur = head;
int result = head->val;
for (int i = 1; cur; i++) {
if (rand()%i == 0) result = cur->val; // 1/i probability to change
cur = cur->next;
}
return result;
}
private:
ListNode* head;
};
```