问题：有一个未知长度的链表，要求在其中随机抽取k个节点作为样本（即如果有n个节点，则每个节点被取出的概率是k/n，而n是未知的）。链表只能顺序读取一遍。（保证链表节点数>k）

思路：先取出前k个节点，以后没到一个节点，就以一定的概率将其与已取出的k个节点随机交换。

具体来说，记链表为A，从A[1]一直扫到A[K]，并取出作为最初的k个节点，记为B。

继续往下扫，扫到A[i](i>k)时，以k/i的概率将其取出，并与B中的某个节点交换（B中有k个节点，每个节点被换出的概率都是相等的，即1/k）；如果A[i]没被取出（概率为(i-k)/i），就继续往下扫。

最后扫完A，得到的B即为所求。

证明：对任意i（i>k）,我们证明其最终出现在B中的概率为k/n（n是A的长度，可以是任意值）。

 扫到A[i]时，他被取出的概率是k/i, 这样他就暂时在B中了，但往后扫的过程中A[i]还可能被换出来。扫到A[i+1]时，A[i]还在B中的概率是(k/i)*[( 1-k/(i+1) )+(k/(i+1))*((k-1)/k)] , 其中( 1-k/(i+1) )是A[i+1]根本就未被取出来的概率，(k/(i+1))*((k-1)/k)是A[i+1]被取出来但没把A[i]换出去的概率。 上式 = k/(i+1), 一次类推，到最后一个即A[n]后，A[i]还在B中的概率为k/n。

证毕。