382. Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen. Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? Example: // Init a singly linked list [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. solution.getRandom();

对于随机数的题目我们一般是确定随机范围，产生随机数，然后查找并做相关操作，所以这题的基本解法可以是先求出链表长度，然后确定随机数后查找该项。 具体代码如下：

方法一：获取链表长度

class Solution { private: ListNode* head; 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): head(head) { } /** Returns a random node's value. */ int getRandom() { int count = 0; ListNode* p = head; while (p != NULL) { count++; p = p->next; } p = head; int j = rand() % count; int i = 0; while (i < j) { p = p->next; i++; } return p->val; } };

方法二：水塘抽样

这也是这题的价值所在，我就是在这学到了水塘抽样。也就是如何在抽样总量特别大的时候，或者说无法确定总量大小的情况下，完成k个样本的抽样，并保证每个个体被等概率抽中。算法如下： S从0开始计数：

從S中抽取首k項放入「水塘」中 對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0到j的整數r 若 r < k 則把水塘中的第r項換成S[j]項

具体数学证明大家自行查找，但这种抽样算法还是值得我们记住的。而这题就相当于是k=1的情况，所以从第二项开始产生0到1的随机数，如果是0，那么candidate为第二项，第三项的时候产生0，1，2之间的随机数，如果是0，替换，以此类推。代码如下：

class Solution { private: ListNode* head; 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): head(head) { } /** Returns a random node's value. */ int getRandom() { int res = head->val; ListNode* p = head->next; int i = 2; while (p) { int r = rand() % i; if (r == 0) res = p->val; p = p->next; i++; } return res; } };