We calculate the len of linked list in the constructed step.

```
class Solution {
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
realHead = head;
while (head->next != NULL) {
head = head->next;
len++;
}
}
/** Returns a random node's value. */
int getRandom() {
int r = rand() % len;
ListNode *p = realHead;
for (int i=0; i<r; i++)
p = p->next;
return p->val;
}
private:
int len = 1;
ListNode *realHead = NULL;
};
```