前言
今天刷leetcode看到一道题，简单介绍下，就是说给定一个未知长度的链表的头节点，让你随机返回其中一个节点的值，这个题目暴力一点的做法是先遍历一遍链表，知道长度之后再进行操作，不过这个办法显然不是best practice，下面我们来介绍下更好的办法，也就是今天我想介绍的一个算法。
简单情景
这里的就按照题目给的要求来做吧，先给定结论，由于我们未知链表的长度，所以遍历的时候保存当前已经遍历的长度，记为n，那么对于链表中的第n个节点，我们选中这个节点的概率只要是1/n就可以保证对于未知长度的链表，能够以相同的概率返回链表中的任意一个节点。
证明
这里的证明我就用数学归纳法来进行证明：（忘了数学归纳法的自行百度哈，这个是高中数学基础）
显然当n=1时，1/1=1，也就是说第一个节点是肯定会被选中，这个是没毛病的。
假设当链表的长度为n的时候，每个节点被选中的概率是1/n，那么现在我们需要证明当链表长度为n+1时，
我们以1/（n+1）的概率选中最后一个节点的值，则每个节点被选中的概率都是1/（n+1），这个也不难证明，
当链表长度为n+1时，前面n个节点中的任意一个节点被选中的概率为（1/n）*（n/（n+1））= 1/（n+1），
这个也不难理解，只有当这个节点在之前被选中，即概率为1/n，且第n+1个节点没有被选中，
即概率为n/（n+1），这个节点才会被选中，所以概率就是1/（n+1），证明完毕。
推广情况
假设链表长度未知，这次我们需要随机选择链表中的k个数字，这个根据前面的结论，猜都能猜到，
对于长度为n（n>=k）的链表，最后一个节点被选中的概率为k/n就能保证从链表中随机选择出k个节点。
推广证明
这里的证明也是数学归纳法，说到这个多说一句，感觉数学里面的证明反证法和数学归纳法在后期
用的越来越多，实在是好用
显然当n=k时，前面k个节点都会被选中，这个也没毛病
假设当链表长度为n的时候，每个节点被选中的概率是k/n，那么我们现在需要证明
当链表长度为n+1时，我们以k/（n+1）的概率选中最后一个节点，那么每个节点被选中
的概率都是k/（n+1），这个证明也不复杂，不过要注意考虑全面，不要漏考虑情况，
否则会导致计算出来的概率不对，下面我从任一节点被选中和未被选中两个角度，证明结论。计算前面n个节点任意一个节点被选中的概率，这个结果会在什么情况下产生呢，
首先肯定要求这个节点在之前就是被选中的节点，否则最后肯定不是被选中的节点，
所以k/n的概率是大前提，进一步考虑，当最后一个节点被选中需要随机替换前面
k个节点中一个的时候，这个节点肯定不能是被选中的，因此这种情况的概率是
k/（n+1）*（k-1）/k，再考虑一下，如果最后一个节点没有被选中，那么这个
节点最后是不是也是被选中了，这种情况的概率是1-（k/（n+1）），综上，一个
节点被选中的概率是k/n * {(k/(n+1) * (k-1)/k + 1 - (k/(n+1)))} = k/(n+1)计算前面n个节点任一节点未被选中的概率，这个结果又会在什么情况下产生呢，
有两种情况，第一种情况是在前面n个节点中这个节点就没被选中，
一开始就比较背（笑），第二种情况是在前面n个节点中这个节点被选中了，
但是第n+1个节点被选中了，且此节点恰好被第n+1个节点替换掉了，这次更背
了（笑），这两种情况的概率加在一起的概率就是该节点未被选中的概率，综上，
一个节点未被选中的概率为1 - k/n + k/n * k/(n+1) * 1/k = 1 - k/(n+1)
总结
到这里算法就介绍的差不多了，这个算法其实并不难理解和证明，但是如果真的是第一次接触的话，其实一下子能想出来的人估计也是凤毛麟角，这里简单介绍一下，数学和计算机结合还是很有意思的。