在链表中等概率选取元素

1. 在链表中等概率选取一个元素

代码：

nmatch = 0;
for (p = list; p != NULL; p = p->next)
if (rand() % ++nmatch == 0)
selected = p;

return selected;

解释：
对第 k 个节点(从 k=1 开始计数，最大为链表长度n)，它被选中的情况是 selected = p; 被执行，并且后面的所有节点都不执行这一句，其概率为
1 1 1 1 1
- * (1- ---) * (1- ---) * ... * (1- -) = -
k k+1 k+2 n n