题目描述
思路解析动画文字版
最朴素的想法是 dict 存 key-value、再用一个数组记录使用顺序。查值很快，但把一个 key 挪到最新、或删掉最旧 key 时，数组要搬一大片元素，最坏是大 O n。
转折：哈希表 cache 让任意 key 都能 O(1) 找到它的链表节点；双向链表维护使用顺序，HEAD 后面是最久未使用，TAIL 前面是最近使用。下面动画上行是链表顺序，下行是哈希表 cache。
初始化 capacity=2：哨兵 HEAD 和 TAIL 先牵手：手写时用 HEAD 和 TAIL 两个哨兵节点夹住所有真实节点，这样删除和插入永远有左右邻居，不用写 null 判断。中间的空槽只是布局占位。
put(1,1)：新节点接到 TAIL 前面，成为最新：新 key 一律插到 TAIL 前面，代表它刚被用过。同时哈希表登记 key=1 指向这个节点。
put(2,2)：容量刚好满，顺序是 1 → 2：容量满了。链表从左到右是 1、2，所以下次淘汰会拿 HEAD 后面的 1。
get(1)：哈希表 O(1) 直接拿到节点 1：哈希表负责 O(1) 定位，不需要从 HEAD 一个个走到 1。命中后还要刷新它的使用顺序，下面三帧慢放这套指针手术。
_remove(节点1) 第1刀：让左邻 HEAD 越过 1 指向右邻：删一个节点要断它的左右两根 next/prev。第一刀：让它的左邻 HEAD 的 next 直接跳过 1、指向 1 的右邻 2。注意 HEAD 通向 1 的箭头已经断开。
_remove(节点1) 第2刀：让右邻 2 的 prev 回指 HEAD，节点 1 脱链：第二刀：让右邻 2 的 prev 回指 HEAD。现在节点 1 左右两根指针都被绕过去了，它彻底脱链——但 cache[1] 还指着它，所以不会丢，等会儿原封不动接到尾部。
_add_to_tail(节点1) 第3刀：把摘下的 1 缝回 TAIL 前面：把节点 1 接到 TAIL 前面，要接四根指针：原尾巴 2 的 next 指向 1、1 的 prev 指向 2、1 的 next 指向 TAIL、TAIL 的 prev 指向 1。顺序从 1、2 变成 2、1。整套删除加插入只改了常数条指针，所以是 O(1)，get 返回 1。
put(3,3)：先接到尾部，出现临时超容量 [2,1,3]：先把 3 接到 TAIL 前面，链表临时变成 3 个真实节点。容量只有 2，所以下一步必须淘汰 HEAD 后面的 LRU，也就是 2。
淘汰 LRU=2：删 head.next 并从 cache 抹掉 key=2：超容量时，lru = head.next，就是 HEAD 后面那个节点 2。链表里用同一套指针手术摘掉它，再 del cache[2]——链表和哈希表必须同步删，少删一个就会内存泄漏或读到脏 key。
get(2)：cache 里查不到，直接返回 -1：未命中的 get 不改变任何顺序，这就是官方输出里的第一个 -1。
put(4,4) 触发淘汰：插 4、踢掉 LRU=1，剩 [3,4]：和淘汰 2 是同一套动作：先把 4 接到 TAIL 前，临时是 1、3、4 三个；超容量就删 head.next=1 并 del cache[1]。所以接着 get(1) 又是 -1，对应官方输出的第二个 -1。
get(3) 命中：3 用同样的手术挪到最新端：访问 3 也算一次使用：摘下、接尾，3 变最新、4 变最旧。这一步底层就是前面慢放的三刀指针手术，只是这里直接给结果。返回值 3。
get(4) 命中：4 移到最新端，返回 4：访问 4 后 4 又回到最右。官方序列最后两个返回值就是 3 和 4。
LRU 的不变量：链表左端永远最久未使用、右端永远最近使用；每次 get 命中和 put，都把对应节点先 _remove 再 _add_to_tail，刷新到右端。
边界三连：LRU 的边界先看最小规模、未命中、和覆盖更新这三种最容易写错分支的情况。
面试追问：把动画里的状态定义、指针手术、哨兵作用讲成自己的话，就能接住这些追问。
参考代码
class Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = Noneclass LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): node.prev.next = node.next node.next.prev = node.prev def _add_to_tail(self, node): prev = self.tail.prev prev.next = node node.prev = prev node.next = self.tail self.tail.prev = node def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._add_to_tail(node) return node.value def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.value = value self._remove(node) self._add_to_tail(node) return node = Node(key, value) self.cache[key] = node self._add_to_tail(node) if len(self.cache) > self.capacity: lru = self.head.next self._remove(lru) del self.cache[lru.key]复杂度
- get 时间：O(1)，cache 查 key 是 O(1)；命中后 _remove 改 2 根指针、_add_to_tail 改 4 根，都是常数。
- put 时间：O(1)，插入或更新、超容量删 head.next、接到尾部，全是哈希表 O(1) 加常数条指针。
- 空间复杂度：O(capacity)，哈希表和链表里最多同时存 capacity 个 key-value。
可套用的代码模板
这是可背的迁移骨架：把空填上（左邻 next=node.next、右邻 prev=node.prev），并记住“被使用就 touch、超容量删 head.next 同时删哈希表”。460 LFU、设计推特等设计题都套这个。右上角可切 C++ / Java。
# 凡是要求“O(1) 查 + O(1) 调整顺序/淘汰”的设计题，套这个骨架：# 1) 哨兵双向链表：维护顺序，左端=最该淘汰，右端=最新# 2) 哈希表 cache: key -> 链表节点，负责 O(1) 定位def _remove(node): # 改 2 根，绕过自己 node.prev.next = ____ # 左邻 next 跳过 node node.next.prev = ____ # 右邻 prev 跳过 nodedef _add_to_tail(node): # 改 4 根，缝到 tail 前 p = tail.prev p.next = node; node.prev = p node.next = tail; tail.prev = nodedef touch(node): # 任何“被使用”都调它 _remove(node); _add_to_tail(node)# get 命中: touch(node) 再返回值；未命中: 返回 -1# put 命中: 改值 + touch；新增: 建节点 + add_to_tail# 然后 if len(cache) > capacity: 删 head.next 同步 del cache[key]易错点
面试追问把动画讲成自己的话
追问为什么是双向链表，单向不行吗？
追问为什么需要 HEAD/TAIL 两个哨兵？
追问Java 能否直接用 LinkedHashMap？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并 K 个升序链表
LeetCode 23 · 困难 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题