382. Linked List Random Node

做题历程：

1. 2016/Oct/20，本题是第一次做，独立解出，耗时15分钟，但不是最优解

说实话，本题如果是用最普通的方法，求长度，然后求解，有点过于简单，基本就是Easy的水平。。但是，如果采用水塘抽样，这个题对于从没见过的人来说，又有点过于复杂了。。好在解法本身并不难，可以学习一下。。

大致算法：

1. 蓄水池大小为1，整体大小为n(在本题中未知)
2. 则每个元素被选中的可能性为1 / n即该元素在最后时刻仍然在蓄水池中的概率是1 / n
3. 每遍历到一个元素的时候，都有可能拿他替代蓄水池中原有元素，这个概率就是我们要求的，概率选对了，就能保证每个元素被最终留下的概率就是1 / n
4. 假设某一元素最终停留在蓄水池的概率是1 / n，
   • 在最后一步之前，它停留在蓄水池的概率应该是1 / (n - 1)
   • 最后一个元素被选中，且去替代他的概率是(P)
   • 则得出等式: (1 - P) * 1 / (n - 1) = 1 / n
   • 得出P = 1 / n
   • 所以要以当前（蓄水池元素 + 遍历过的元素）的和分之1的概率选出替换元素

之后就是写代码了：

class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
    }

    /** Returns a random node's value. */
    int getRandom() {
        int res = head->val;
        ListNode* node = head->next;
        int i = 1;
        while (node != nullptr) {
            int pos = rand() % (i + 1);
            if (pos == 0) {
                res = node->val;
            }
            ++i;
            node = node->next;
        }
        return res;
    }
private:
    ListNode* head;
};