How about still use rand to generate and get random value [0,k]

Here is my AC solution

public:
Solution(ListNode* head) {
this->mHead = head;
}
int getRandom() {
ListNode* list = mHead;
int k = 1, r = list->val;
while(list->next){
if(randInt(0,k++) == 0) r= list->next->val;
list = list->next;
}
return r;
}
private:
ListNode* mHead;
int randInt(int min, int max) {
float rand_f = (float)rand()/(float)RAND_MAX;
return min + (int)(rand_f*(max-min+1));
}