## 题目描述：

LeetCode 382. Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

```// Init a singly linked list [1,2,3].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
```

## 解题思路：

```I   当链表长度为1时，random.randint(0, 0)恒等于0，因此抽到第1个元素的概率为1

II  假设抽取前n个元素的概率相等，均为1/n

III 当抽取第n+1个元素时：

```

## Python代码：

``````import random
class Solution(object):

"""
@param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
"""

def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
cnt = 0
if random.randint(0, cnt) == 0:
cnt += 1
return ans

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

Pingbacks已关闭。