链表不能随机访问，为什么还能“等概率随机抽一个节点”？这道题真有点东西！作者：Echo_Wish如果我问你一个问题：给你一个单链表，每个节点被抽中的概率都必须完全一样，你怎么实现？很多人的第一反应都是：“先遍历链表放进数组，然后random.choice()不就好了？”确实，这样能做。但是，如果面试官接着补一句：链表特别大，甚至有几亿个节点，内存放不下怎么办？这时候，很多人就开始沉默了。这就是今天要聊的经典算法题——Linked List Random Node（链表随机节点）。这道题看起来只是随机数，实际上考察的是一种非常经典的算法思想——蓄水池抽样（Reservoir Sampling）。很多大厂都喜欢考它，因为它不仅考代码能力，更考察你面对未知数据规模时的算法思维。今天，我们就把这道题彻底讲透。一、题目到底说了什么？LeetCode 382 的题目非常简单。给定一个单链表：