There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).

解答思路：

这是一个关于如何从未知长度的链表中随机选择k个数字的问题。由于链表的长度N是未知的，并且要求时间复杂度为O(n)，我们可以使用“Reservoir Sampling”算法来解决这个问题。该算法的核心思想是在遍历链表的过程中，以一定的概率选择每个元素，使得最终选出的元素个数符合随机分布的要求。

具体步骤如下：

1. 初始化一个大小为k的“reservoir”，用于存储选出的数字。
2. 从链表的第一个元素开始遍历，对于每个遍历到的元素：
   • 以rand()函数生成一个[0, 1)之间的随机数。
   • 如果这个随机数小于等于irand()函数返回的概率值（假设为p），则将当前元素添加到“reservoir”中，并随机替换“reservoir”中的已有元素。这一步确保了每个元素被选中的概率相等。
   • 如果这个随机数大于irand()函数返回的概率值，则不执行任何操作。
3. 当遍历完链表后，“reservoir”中存储的就是随机选取的k个数字。

最优回答：

在函数内部，首先初始化一个大小为k的数组或列表作为“reservoir”。然后遍历链表，对于每个元素，都以rand()函数生成的随机数作为选择依据，如果随机数满足条件（小于等于irand()函数返回的概率值），则将该元素添加到“reservoir”中，并随机替换已存在的元素。最后返回“reservoir”中的元素作为结果。