Leetcode上遇到一道題，題目是這樣的：

這道題的關(guān)鍵是鏈表的長(zhǎng)度不知道，但是要使隨機(jī)返回每個(gè)元素的概率相等，這一下就難倒我了，如果知道鏈表的長(zhǎng)度k，從0到k中隨機(jī)選擇一個(gè)整數(shù)就好了呀，可現(xiàn)在不知道長(zhǎng)度k的值。不過沒關(guān)系，蓄水池抽樣算法給了我們?cè)诓恢篱L(zhǎng)度的情況下，等概率隨機(jī)抽樣的方法。

假設(shè)我們要從一大堆元素中選擇k個(gè)元素，不知道多少，反正很多很多。使用蓄水池抽樣算法的具體的思路是：先初始化一個(gè)集合，集合中有k個(gè)元素，將此集合作為蓄水池。然后從第k+1個(gè)元素開始遍歷，并且按一定的概率替換掉蓄水池里面的元素。偽代碼是這樣的：

Init : a reservoir with the size： k  
for i= k+1 to N  
    M=random(1, i);  
    if( M < k)  
     SWAP the Mth value and ith value  
end for   

具體描述如下：先將前k個(gè)數(shù)取出來(lái)放入結(jié)果集中，然后從第k+1個(gè)數(shù)開始遍歷。假設(shè)遍歷到第i個(gè)數(shù)，以k/i的概率替換掉蓄水池中的某個(gè)元素即可。

是不是很好理解？接下來(lái)，我們來(lái)看看，為什么使用這種算法抽取到每個(gè)元素的概率是相等的，這里我們使用數(shù)學(xué)歸納法：

問題描述：

取前k個(gè)元素放入蓄水池中。從i=k+1開始，以k／i的概率取第i個(gè)元素。若第i個(gè)元素被選中，已均等的概率(即1/k)替換蓄水池中的先前被選中的任一元素。

證明：

這樣，我們就證明了用蓄水池抽樣算法抽取每個(gè)元素的概率是相等的。

問題求解

所以，回到上面的leetcode問題，我們得到的答案如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        result,node,index = self.head,self.head.next,1
        while node:
            if random.randint(0,index) == 0:
                result = node
            node = node.next
            index = index + 1
        return result.val
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()