```
class Solution {
private:
ListNode* curr;
ListNode* newhead;
int length;
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* head) {
curr = head;
newhead = head;
int i = 0;
while(head){
head = head->next;
i++;
}
length = i;
}
/** Returns a random node's value. */
int getRandom() {
int n = rand() % length;
while(n){
if(!curr->next){
curr = newhead;
n--;
}
while(curr && curr->next && n){
curr = curr->next;
n--;
}
}
return curr->val;
}
};
```

Follow up Solution:

```
class Solution {
private:
ListNode* curr;
ListNode* newhead;
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* head) {
curr = head;
newhead = head;
}
/** Returns a random node's value. */
int getRandom() {
int n = rand();
while(n){
if(!curr->next){
curr = newhead;
n--;
}
while(curr && curr->next && n){
curr = curr->next;
n--;
}
}
return curr->val;
}
};
```