算法-统一随机元素链表

Question

如何从链表中获得统一的随机元素？通过计算列表的长度当你在计数时，生成一个随机元素。如果列表的随机元素%长度等于0，然后选择该元素。

Answer 1

在开始挑选元素之前，首先需要列表的长度，因此它平均需要在列表中迭代1.5次。

第一个是获取列表的长度。然后得到一个[0…1]的随机数乘以列表的长度，四舍五入。这是你必须得到的索引（你必须进行另一次迭代）。

在伪代码中：

int n = list.size()  // Returns length of list
int index = (int) (random_value() * n); // random_value returns a value between 0.0 and 1.0
int* node = list.start() // goto start of list
for (int iter = 0; 0 < n; n++)
    node = node->next() // Goto next node
return node