链表 · Linked List

一句话骨架：90% 链表题靠两件事——「哨兵 dummy」处理头节点变更，「快慢双指针」找中点 / 找环 / 找倒数第 K 个。

通用技巧

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

dummy = ListNode(0, head)   # 哨兵：让「删头」「插头」与一般节点同质
prev, curr = dummy, head

三把板斧：

招式	适用场景	关键不变量
dummy 哨兵	头节点会变更（删除/插入头部）	始终有「前驱」可以接
快慢指针	找中点、判环、找倒数第 K	fast 步幅是 slow 的 2 倍
三指针掉头	反转片段	prev → curr → nxt 的暂存顺序不能错

关卡 1 · 反转链表

学习目标

能从空白纸默写出 6 行迭代反转，并讲清「为什么必须三个指针」。

#206反转链表简单

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

要求尽可能用迭代或递归两种方式解决，并理解二者的区别。

示例 1

输入head = [1,2,3,4,5]

输出[5,4,3,2,1]

示例 2

输入head = [1,2]

输出[2,1]

示例 3

输入head = []

输出[]

💡 空链表合法

约束

• 链表中节点数目范围 [0, 5000]
• -5000 ≤ Node.val ≤ 5000

💡 思路：迭代版需要三个指针：prev / curr / nxt。核心动作是「先暂存 next，再掉头当前指针，最后整体推进」——四步缺一不可。递归版本更短：reverse(head.next) 之后，让 head.next.next = head 完成反转。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def reverseList(head: ListNode | None) -> ListNode | None: 6    prev, curr = None, head 7    while curr: 8        nxt = curr.next       # 1. 暂存下一个，避免掉头后丢失 9        curr.next = prev      # 2. 掉头：当前节点指向前一个10        prev = curr           # 3. prev 推进11        curr = nxt            # 4. curr 推进12    return prev               # prev 最终指向原尾节点 = 新头

🐞 单步可视化

示例：head = 1 → 2 → 3 → 4 → 5 → None

代码L6

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def reverseList(head: ListNode | None) -> ListNode | None: 6    prev, curr = None, head 7    while curr: 8        nxt = curr.next       # 1. 暂存下一个，避免掉头后丢失 9        curr.next = prev      # 2. 掉头：当前节点指向前一个10        prev = curr           # 3. prev 推进11        curr = nxt            # 4. curr 推进12    return prev               # prev 最终指向原尾节点 = 新头

数据流

prevNonecurr1nxtNonelinks1→2 2→3 3→4 4→5 5→∅

链表节点

curr

1

→

2

→

3

→

4

→

5

1 / 22初始化 prev=None, curr=head（值 1）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

迭代反转最少需要几个指针变量？

prev 的初始值应该是？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def reverseList(head: ListNode | None) -> ListNode | None: 6    prev, curr = None, head 7    while curr: 8        nxt = curr.next       # 1. 暂存下一个，避免掉头后丢失 9        curr.next = prev      # 2. 掉头：当前节点指向前一个10        prev = curr           # 3. prev 推进11        curr = nxt            # 4. curr 推进12    return prev               # prev 最终指向原尾节点 = 新头

循环体内四步操作的正确顺序是？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def reverseList(head: ListNode | None) -> ListNode | None: 6    prev, curr = None, head 7    while curr: 8        nxt = curr.next       # 1. 暂存下一个，避免掉头后丢失 9        curr.next = prev      # 2. 掉头：当前节点指向前一个10        prev = curr           # 3. prev 推进11        curr = nxt            # 4. curr 推进12    return prev               # prev 最终指向原尾节点 = 新头

循环结束时 prev 指向什么？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def reverseList(head: ListNode | None) -> ListNode | None: 6    prev, curr = None, head 7    while curr: 8        nxt = curr.next       # 1. 暂存下一个，避免掉头后丢失 9        curr.next = prev      # 2. 掉头：当前节点指向前一个10        prev = curr           # 3. prev 推进11        curr = nxt            # 4. curr 推进12    return prev               # prev 最终指向原尾节点 = 新头

空链表（head 为 None）这份代码会发生什么？

递归版反转的核心一行 head.next.next = head 含义是？

递归版的空间复杂度是？

为什么这道题不需要 dummy 哨兵节点？

如果把 prev = None 改成 prev = ListNode(0)，结果会怎样？

迭代版的时间复杂度是？

Python 里 prev, curr = None, head 这种写法叫什么？

若题目改成「反转链表的前 K 个节点」，最直接的改动是？

关卡 2 · 环形链表 II

学习目标

理解 Floyd 判圈两阶段为什么成立，能推导 a = c + (n-1)L。

#142环形链表 II中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中存在环，则返回环入口节点；不允许修改链表，要求空间复杂度 O(1)。

示例 1

输入head = [3,2,0,-4], pos = 1

输出返回索引 1 的节点（值为 2）

💡 pos 表示尾节点连接到链表中的哪个位置

示例 2

输入head = [1,2], pos = 0

输出返回索引 0 的节点（值为 1）

示例 3

输入head = [1], pos = -1

输出null

💡 无环

约束

• 链表中节点的数目范围在 [0, 10⁴]
• -10⁵ ≤ Node.val ≤ 10⁵
• pos ∈ [-1, n-1]，-1 表示无环

💡 思路：Floyd 判圈两阶段：① 快慢指针 fast 走 2 步、slow 走 1 步，若有环必相遇；② 把一个指针放回 head，两者**同速**前进，再次相遇就是入口。数学推导：设头到入口距离 a，入口到相遇点距离 b，相遇点回到入口距离 c，环长 L=b+c。fast 走 2(a+b) = a+b+nL（n 是 fast 在环内多绕的圈数）⇒ a = c + (n-1)L。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def detectCycle(head: ListNode | None) -> ListNode | None: 6    slow = fast = head 7    # 阶段一：快慢指针在环内相遇 8    while fast and fast.next: 9        slow = slow.next10        fast = fast.next.next11        if slow is fast:12            break13    else:14        return None                # 走到尽头说明无环15    if not (fast and fast.next):16        return None                # 兼容 break 后再判断的情况17 18    # 阶段二：把任一指针放回 head，同速前进，再次相遇即入口19    slow = head20    while slow is not fast:21        slow = slow.next22        fast = fast.next23    return slow                    # 数学结论：a = c + (n-1) * L

🐞 单步可视化

示例：head = [3,2,0,-4], pos = 1（尾节点 -4 连回 idx=1 即值 2）

代码L6

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def detectCycle(head: ListNode | None) -> ListNode | None: 6    slow = fast = head 7    # 阶段一：快慢指针在环内相遇 8    while fast and fast.next: 9        slow = slow.next10        fast = fast.next.next11        if slow is fast:12            break13    else:14        return None                # 走到尽头说明无环15    if not (fast and fast.next):16        return None                # 兼容 break 后再判断的情况17 18    # 阶段二：把任一指针放回 head，同速前进，再次相遇即入口19    slow = head20    while slow is not fast:21        slow = slow.next22        fast = fast.next23    return slow                    # 数学结论：a = c + (n-1) * L

数据流

phase① 找相遇点slowidx=0, val=3fastidx=0, val=3

节点（按原始下标；尾节点 idx=3 连回 idx=1）

slowfast

3

→

2

→

0

→

-4

→

↺ 回到 idx=1

1 / 20初始化 slow = fast = head（idx=0, val=3）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么 fast 走 2 步而 slow 走 1 步，而不是 3 步和 1 步？

while fast and fast.next: 这两个条件分别防止什么？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def detectCycle(head: ListNode | None) -> ListNode | None: 6    slow = fast = head 7    # 阶段一：快慢指针在环内相遇 8    while fast and fast.next: 9        slow = slow.next10        fast = fast.next.next11        if slow is fast:12            break13    else:14        return None                # 走到尽头说明无环15    if not (fast and fast.next):16        return None                # 兼容 break 后再判断的情况17 18    # 阶段二：把任一指针放回 head，同速前进，再次相遇即入口19    slow = head20    while slow is not fast:21        slow = slow.next22        fast = fast.next23    return slow                    # 数学结论：a = c + (n-1) * L

Floyd 第二阶段「a = c + (n-1)L」中 a、c、L 分别代表？

为什么第二阶段两个指针同速前进就能在入口相遇？

判断「相遇」用 slow is fast 还是 slow == fast 更严谨？

若链表无环，第一阶段 while 循环如何退出？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def detectCycle(head: ListNode | None) -> ListNode | None: 6    slow = fast = head 7    # 阶段一：快慢指针在环内相遇 8    while fast and fast.next: 9        slow = slow.next10        fast = fast.next.next11        if slow is fast:12            break13    else:14        return None                # 走到尽头说明无环15    if not (fast and fast.next):16        return None                # 兼容 break 后再判断的情况17 18    # 阶段二：把任一指针放回 head，同速前进，再次相遇即入口19    slow = head20    while slow is not fast:21        slow = slow.next22        fast = fast.next23    return slow                    # 数学结论：a = c + (n-1) * L

能不能用「哈希表存访问过的节点」替代 Floyd？

slow = fast = head 这种链式赋值的语义？

 1class ListNode: 2    def __init__(self, val=0, next=None): 3        self.val, self.next = val, next 4  5def detectCycle(head: ListNode | None) -> ListNode | None: 6    slow = fast = head 7    # 阶段一：快慢指针在环内相遇 8    while fast and fast.next: 9        slow = slow.next10        fast = fast.next.next11        if slow is fast:12            break13    else:14        return None                # 走到尽头说明无环15    if not (fast and fast.next):16        return None                # 兼容 break 后再判断的情况17 18    # 阶段二：把任一指针放回 head，同速前进，再次相遇即入口19    slow = head20    while slow is not fast:21        slow = slow.next22        fast = fast.next23    return slow                    # 数学结论：a = c + (n-1) * L

当环极小（L=1，单节点自环）时这份代码会？

本算法的时间复杂度是？

如果把第二阶段「slow 回到 head」改成「fast 回到 head」，结果如何？

Python 的 while ... else 在哪些时机进入 else？

关卡 3 · 合并 K 个升序链表

学习目标

说清「O(N log K) vs O(N log N)」的差别，知道 Python 堆为什么要塞 tiebreaker。

#23合并 K 个升序链表困难

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1

输入lists = [[1,4,5],[1,3,4],[2,6]]

输出[1,1,2,3,4,4,5,6]

示例 2

输入lists = []

输出[]

示例 3

输入lists = [[]]

输出[]

💡 只有空链表也合法

约束

• k == lists.length
• 0 ≤ k ≤ 10⁴
• 0 ≤ lists[i].length ≤ 500
• lists[i][j] 升序排列且 -10⁴ ≤ lists[i][j] ≤ 10⁴

💡 思路：两条主流：① **最小堆**——把每条链表的当前头入堆，每次弹最小、把它的 next 入堆，O(N log K)；② **分治两两合并**，类似归并排序合并，O(N log K)。两者复杂度同，堆胜在思路直观。注意 Python 堆需要解决「ListNode 不可比较」问题——元组里塞个唯一索引 i 当 tiebreaker。

✅ 完整解法

时间 O(N log K) · 空间 O(K)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

🐞 单步可视化

示例：lists = [[1,4,5],[1,3,4],[2,6]]

代码L9

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

数据流

K3heap.size0heap空merged空

lists[0]（剩余: 3）

L0

1

→

4

→

5

lists[1]（剩余: 3）

L1

1

→

3

→

4

lists[2]（剩余: 2）

L2

2

→

6

合并结果（dummy → tail）

tail

dummy

1 / 38初始化 heap = [], dummy 哨兵, tail = dummy

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么堆解法的时间复杂度是 O(N log K) 而非 O(N log N)？（N 总节点数，K 链表数）

为什么 heappush 的元组里要放 i（链表索引）作为第二位？

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

dummy 哨兵节点在这道题里的作用？

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

弹出堆顶后，下一步关键操作是？

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

初始入堆时为什么要 if node: 判断？

 1import heapq 2  3class ListNode: 4    def __init__(self, val=0, next=None): 5        self.val, self.next = val, next 6  7def mergeKLists(lists: list[ListNode | None]) -> ListNode | None: 8    # 用堆维护当前每条链表的「最前未取节点」；总共 N 节点、K 条链 9    heap = []10    for i, node in enumerate(lists):11        if node:12            # 元组里第二位放 i 是「打破值相等时的比较僵局」——13            # 因为 ListNode 没有定义 __lt__，直接比较两个节点会 TypeError14            heapq.heappush(heap, (node.val, i, node))15    dummy = ListNode(0)16    tail = dummy17    while heap:18        val, i, node = heapq.heappop(heap)19        tail.next = node20        tail = node21        if node.next:22            heapq.heappush(heap, (node.next.val, i, node.next))23    return dummy.next

Python heapq 是哪种堆？

分治版「两两合并」的时间复杂度也是 O(N log K) 而非 O(NK)，关键原因是？

空间复杂度 O(K) 来自？

为什么不能直接 heapq.heappush(heap, node)（只放节点不放元组）？

把所有节点先全部入堆再依次弹（不动态补）的复杂度？

heapq.heappop(heap) 返回什么？

相比堆解法，分治两两合并的优势是？

如果 lists 全是 None（每条链都是空），代码会？

关卡 4 · LRU 缓存

学习目标

能徒手设计「哈希 + 双向链表」的 O(1) 缓存，并解释为什么单向链表不够。

#146LRU 缓存中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过容量 capacity，则应该逐出最久未使用的关键字

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例 1

输入LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)

输出1, -1, -1, 3, 4

💡 容量 2，put(3) 时淘汰 key=2；之后 put(4) 淘汰 key=1

约束

• 1 ≤ capacity ≤ 3000
• 0 ≤ key ≤ 10⁴
• 0 ≤ value ≤ 10⁵
• 调用次数最多 2 × 10⁵ 次

💡 思路：哈希表 + 双向链表是 O(1) 的「黄金组合」：哈希表把 key 映射到「节点指针」（O(1) 定位）；双向链表维护使用顺序（O(1) 摘除/接入）。head 端永远是「最新」，tail 端永远是「最久」。Python 也有偷懒解：`collections.OrderedDict` + `move_to_end`。

✅ 完整解法

时间 O(1) 每次操作 · 空间 O(capacity)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

🐞 单步可视化

示例：LRUCache(2); put(1,1); put(2,2); get(1)→1; put(3,3) 淘汰 key=2; get(2)→-1

代码L7

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

数据流

cap2size0cache空

双向链表（H = head 哨兵，T = tail 哨兵；H 端=最新，T 端=最旧）

H

→

T

1 / 20LRUCache(capacity=2)：cap=2, cache={}

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么必须是双向链表，而不是单向？

哈希表里存的是「key → 值」还是「key → 节点指针」？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

head 和 tail 两个哨兵节点的作用？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

get(key) 命中后必须做什么才符合 LRU 语义？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

put 时如果 key 已存在，正确的处理是？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

超容量时淘汰哪一端？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

为什么节点要存 key（而不是只存 value）？

_remove(node) 的两行赋值顺序能交换吗？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

Python 的偷懒写法是什么？

get 和 put 都做到 O(1) 的关键是？

内存上看，capacity = 3000 时大约占用？

_add_to_head 中四行赋值的顺序敏感吗？

 1class Node: 2    def __init__(self, key=0, val=0): 3        self.key, self.val = key, val 4        self.prev = self.next = None 5  6class LRUCache: 7    def __init__(self, capacity: int): 8        self.cap = capacity 9        self.cache: dict[int, Node] = {}     # key → 节点指针10        # 双向链表：头部「最近使用」，尾部「最久未用」11        self.head, self.tail = Node(), Node()12        self.head.next = self.tail13        self.tail.prev = self.head14 15    def _remove(self, node: Node) -> None:16        node.prev.next = node.next17        node.next.prev = node.prev18 19    def _add_to_head(self, node: Node) -> None:20        node.next = self.head.next21        node.prev = self.head22        self.head.next.prev = node23        self.head.next = node24 25    def get(self, key: int) -> int:26        if key not in self.cache:27            return -128        node = self.cache[key]29        self._remove(node)30        self._add_to_head(node)              # 命中即「挪到表头」31        return node.val32 33    def put(self, key: int, value: int) -> None:34        if key in self.cache:35            node = self.cache[key]36            node.val = value37            self._remove(node)38            self._add_to_head(node)39            return40        if len(self.cache) >= self.cap:      # 超容量 → 淘汰表尾41            lru = self.tail.prev42            self._remove(lru)43            del self.cache[lru.key]44        node = Node(key, value)45        self.cache[key] = node46        self._add_to_head(node)

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
160	相交链表	简单	双指针「a→b、b→a」走完终在交点（或 None）相遇
21	合并两个有序链表	简单	dummy + 双指针逐个比；merge-K 的子函数
2	两数相加	中等	双指针逐位相加 + 进位；注意进位最后一位
19	删除链表的倒数第 N 个结点	中等	快慢指针，fast 先走 N 步再同速；务必用 dummy 防删头
24	两两交换链表中的节点	中等	dummy + 三指针；递归两行也很优雅
25	K 个一组翻转链表	困难	反转链表的进阶版——分段反转 + 接回
138	随机链表的复制	中等	哈希「原节点 → 新节点」或「原地穿插再拆」
148	排序链表	中等	归并排序：快慢找中点 + merge two lists
141	环形链表 I	简单	Floyd 判圈第一阶段
234	回文链表	简单	找中点 + 反转后半 + 双指针对比

面试常踩

• 指针操作顺序错位：反转链表里漏掉 nxt = curr.next 暂存，第二步 curr.next = prev 立刻丢失对后续节点的引用。
• 链表对象比较用 is 不是 ==：节点 val 可能重复，比较「是不是同一对象」必须用 is。
• dummy 不是万能但常常香：删头 / 在头前插入 / 多链合并 / 链表分组，都用 dummy 让边界统一。
• Floyd 判圈的速度差为什么是 1：差为 1 才能保证「相遇 + 第二阶段同速回头」的数学结论成立；3:1 仍能判环但定位不到入口。
• LRU 节点必须存 key：淘汰节点时要回头从哈希表 del key，不存 key 就找不回去——典型设计陷阱。