手写跳表(LeetCode 1206)
哪些公司问过
答案要点
- 结构:多层有序链表,底层含全部元素,节点保存各层 next 指针
- 查找:从最高层开始右移,下一节点不小于目标时下降一层
- 插入:记录每层前驱 update[],随机层数(如概率 1/2 晋升、设最大层),逐层链接
- 删除:找到各层前驱后逐层摘除,可同步降低当前层高
- 期望时间 O(log n),空间期望 O(n),实现比平衡树简单
易错点
- 插入时没有记录每层前驱,导致只更新了底层
- 层数无限增长,没有设置最大层数
- 查找时比较条件写成大于等于,跳过了等于目标的节点
面试官常见追问
- 跳表和红黑树相比有什么优劣?
- Redis 的有序集合为什么用跳表?
- 允许重复元素时怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。