I generate the a number for each node and return the node with the highest generated value.

Each node has a 1/n probability of generating the largest value and thus has a 1/n probability of being returned.

```
int getRandom() {
int maxNumber = 0;
int maxNodeValue = 0;
ListNode * current = head;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 1000000000);
while(current != NULL) {
int rand = dis(gen);
if(rand > maxNumber) {
maxNumber = rand;
maxNodeValue = current->val;
}
current = current->next;
}
return maxNodeValue;
}
```