水塘抽样：

    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.     ListNode* h;
    11. public:
    12.     /** @param head The linked list's head.
    13.         Note that the head is guaranteed to be not null, so it contains at least one node. */
    14.     Solution(ListNode* head) {
    15.         h = head;
    16.     }
    18.     /** Returns a random node's value. */
    19.     int getRandom() {
    20.         auto cur = h;
    21.         int val = cur->val, len = 0;
    22.         while(cur)
    23.         {
    24.             if(rand() % (len + 1) == 0)
    25.                 val = cur->val;
    26.             len++;
    27.             cur = cur->next;
    28.         }
    29.         return val;
    30.     }
    31. };
    33. /**
    34.  * Your Solution object will be instantiated and called as such:
    35.  * Solution* obj = new Solution(head);
    36.  * int param_1 = obj->getRandom();
    37.  */