> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/16_math/382.-linked-list-random-node.md).

# 382. Linked List Random Node

<https://leetcode.com/problems/linked-list-random-node/description/>

## solution

```python
# 直接思路：将链表转化为数组，然后通过数组下标实现O(1)的随机取
# Reservoir Sampling思路: 当链表长度未知且只能用常数空间，采用蓄水池算法. (很适合链表无法一次性取到全部, 类似stream)

class Solution(object):
    def __init__(self, head):
        self.head = head

    def getRandom(self):
        count = 0
        res = None

        cur = self.head
        while cur:
            if random.randint(0, count) == 0:
                res = cur.val
            count += 1
            cur = cur.next

        return res
```

时间复杂度：O(n)\
空间复杂度：O(1)

## follow up

[随机类小结](/mle-interview/01_leetcode/16_math/398.-random-pick-index.md)