手撕代码题：有一个链表不能放到内存中，有 getNext 函数可以取下一个数据，next 函数可以判断是否还有下一个，需要随机等概率取出 K 个节点，要求链表只能扫描一遍，不能重复扫描，各个节点之间被选择必须是独立的。
考察说明
考察蓄水池抽样算法的理解与实现，以及随机性、等概率、单遍扫描等约束的把握
回答思路
- 能明确指出用蓄水池抽样解决单遍等概率抽样
- 正确实现先填充前K个再逐步替换的逻辑
- 能说明替换概率的推导，保证每个节点被选中的概率为K/n
- 能处理边界条件：n<K或K=0时的情况
- 能说明如何用随机数保证独立性
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。