382. 链表随机节点（中等）

方法一

思路

• 定义两个链表，一个origin，用于每次调用 getRandom() 时进行初始化，一个 l 用于每次调用 getRandom() 时进行遍历，找到随机选定的元素。
• 首先在 Solution() 的时候，使用 head 对于两个链表初始化，并对链表进行一次遍历，得到链表的长度；
• 随机元素的选取：定义下标 pos，其范围在 [0, len-1] 之间。

注意

• 在遍历链表得到随机元素的时候，条件需要严格限制，特别是链表一定得是非空。
• 其实这道题不够严谨，按照方法二的分析，如果题目加上“只允许遍历一次”的条件，那么我这个方法就不通过了，我进行了两次遍历，所以还是要学习蓄水池抽样算法。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* l;
    ListNode* origin;
    int len=0;
    Solution(ListNode* head) {
        // 初始化
        l = origin = head;
        while(l != nullptr){
            len ++;
            l = l->next;
        }
    }
    
    int getRandom() {
        int pos = rand() % len;
        // 复原链表     
        l = origin;
        while(pos-- && l != nullptr && l->next != nullptr){
           l = l->next;
        }
        return l->val;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

方法二： 蓄水池抽样算法

蓄水池抽样算法介绍

当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。

该方法适用于只允许一次遍历链表的情况！

这道题的 k=1，也就是我们每次只能选取 1 个数据。假设数据流含有 N 个数，我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为 1/N 。

那如何保证呢？

• 从前往后处理每个样本，每个样本成为答案的概率为 1/i​，其中 i 为样本编号（编号从 1 开始），最终可以确保每个样本成为答案的概率均为 1/n（其中 n 为样本总数）。
• 容易证明该做法的正确性，详见参考资料2 。

思路

• 在每一次 getRandom 时，从前往后处理每个节点，同时记录当前节点的编号，当处理到节点 k（k 从 1 开始） 时，在 [0,k) 范围内进行随机，若随机到结果为 0（发生概率为 1/k），则将节点 k 的值存入答案，最后一次覆盖答案的节点即为本次抽样结果。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    Solution(ListNode* head) {
        // head只存放地址
        this->head = head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* phead = this->head;
        int val = phead->val;
        int count = 1;
        while (phead){
        	// 如果 rand() % count++ == 0
        	// 说明此时的概率为 1/count(k)
        	// 那么就对这个值进行替换
            if (rand() % count++ == 0)
                val = phead->val;
            phead = phead->next;
        }
        return val;
    }
    ListNode* head;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

参考资料

1. 蓄水池抽样算法

2. 【宫水三叶】蓄水池抽样运用题