382. Linked List Random Node

In first place, I don't have any clue. Then I followed the top rated solution which uses "reservoir sampling". Here is the wiki page for this algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling.

For example, the list is 1->2->3.
1. First of all , we keep 1st node. in the list. The probability is 1.

2. We reach the 2nd node. We have two choices:
(1). keep the current node. Then the probability is 1/2
(2). discard the current node, keep the 2nd node. Then the probability is 1/2.

3. We reach the 3rd node. We have two choices:
(1). keep the current node. So the probability for discarding the 3rd node is 2/3. Since the current node could be 1st node or 2nd node, the probability for keeping the current node is 1/2*2/3 = 1/3.
(2). keep the 3rd node. So the probability is simply 1/3.

By introduction, it is easy to prove that when there is n nodes, each node is kept for probability 1/n. With this in mind, here is the solution:

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  private:  
11:    ListNode *head = NULL;  
12:  public:  
13:    /** @param head The linked list's head.  
14:      Note that the head is guaranteed to be not null, so it contains at least one node. */  
15:    Solution(ListNode* head) {  
16:      this->head = head;  
17:    }  
18:    /** Returns a random node's value. */  
19:    int getRandom() {  
20:      ListNode *cur = head->next;  
21:      ListNode *res = head;  
22:      for (int n = 2; cur != NULL; n++) {  
23:        if (rand() % n == 0) res = cur;  
24:        cur = cur->next;  
25:      }  
26:      return res->val;;  
27:    }  
28:  };  
29:  /**  
30:   * Your Solution object will be instantiated and called as such:  
31:   * Solution obj = new Solution(head);  
32:   * int param_1 = obj.getRandom();  
33:   */