如何让链表查找达到O(1)
哪些公司问过
答案要点
- 链表不支持随机访问,按值查找只能顺序遍历,时间O(n)
- 哈希表存key到节点指针的映射,查找平均O(1),链表负责维护顺序
- 用双向链表,拿到节点后可O(1)删除,无需遍历找前驱
- 典型应用是LRU缓存,get/put均为O(1);Java的LinkedHashMap即此结构
- 代价是额外空间,且O(1)是平均复杂度,哈希冲突严重时会退化
易错点
- 用单链表实现删除,找前驱又退化为O(n)
- 淘汰节点时只删链表不删哈希表项,留下悬空指针
- 把哈希表的平均O(1)说成最坏情况也是O(1)
面试官常见追问
- LRU的get和put具体怎么做?
- 为什么链表节点里也要存key?
- 如果还要支持有序和范围查询呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。