🔗 01-数据结构与算法 · 主题 3:链表¶
链表是指针操作的试金石,也是手撕题最爱的载体(反转、环、LRU)。 本 notebook 目标:建立指针心智 → 背熟反转/判圈/哑节点模板 → 吃透 7 道高频题 → 通过 25 道自测。
前置:主题 1、2(数组/哈希)。运行环境:Python 3.8+,无第三方依赖。
核心概念¶
(a) 🗂️ 链表:指针心智、反转/判圈/哑节点模板与 7+2 道高频题¶
链表是"指针操作"的试金石,也是手撕题最爱的载体(反转、判圈、LRU)。本 notebook 建立指针心智,背熟反转/判圈/哑节点模板,精讲高频题并补充 2 道扩展题。
flowchart TB
N1["🔗 链表:指针操作试金石"] --> N2["链表 vs 数组(复杂度心智)"]
N1 --> N3["反转链表 206:迭代 + 递归"]
N1 --> N4["环形链表 141/142:Floyd 判圈"]
N3 --> N5["合并/相交链表:21 / 160"]
N2 --> N6["LRU 缓存 146:哈希 + 双向链表"]
N3 --> N7["K 个一组翻转 25 / 回文 234"]
N5 --> N8["哑节点与常见坑"]
N7 --> N8
N8 --> N9["复杂度总表与自测"]
- N1 · 链表:指针操作试金石:链表由一个个"节点 + 指针"串起来,操作的是内存里的引用关系。秋招手撕最爱考反转、判圈、LRU——因为写错一个指针就全盘皆输。
- N2 · 链表 vs 数组:数组随机访问 O(1)、链表 O(n);但链表在已知节点时插入/删除是 O(1)。"用空间换灵活性"是链表的核心心智,做题前先比这张表。
- N3 · 反转链表 206:最经典的递推:迭代版三指针 prev/cur/nxt 逐个掉头;递归版先把后面反转好再处理当前节点,两条路都要会默写。
- N4 · 环形链表 141/142:快慢指针判断有没有环;若相遇,再用"从头部和相遇点同步走"找入环节点——Floyd 判圈的数学推导面试常问。
- N5 · 合并/相交链表:合并两个有序链表是递归模板题;相交链表用"两链表末尾对齐 + 同步走"的双指针公式。
- N6 · LRU 缓存 146:哈希表定位 + 双向链表维护访问顺序,是"数据结构组合拳"的代表作,也是面试手撕频率最高的题之一。
- N7 · K 个一组翻转/回文链表:K 个一组翻转考"分块 + 子问题反转 + 重新接线";回文链表用快慢指针找中点 + 反转后半段再对比。
- N8 · 哑节点与常见坑:哑节点(dummy)专门解决"头节点可能被改"的问题,能让代码少一半边界判断;链表题 90% 的 bug 出在空指针与断链顺序。
- N9 · 复杂度总表与自测:背熟复杂度总表,把反转/判圈/哑节点模板练到肌肉记忆,再按 L1/L2/L3 自测清单逐项过关。
§1 心智模型与复杂度¶
链表 vs 数组¶
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问第 $i$ 个 | $O(1)$ | $O(n)$(必须从头走) |
| 头部插入/删除 | $O(n)$(搬移) | $O(1)$ |
| 已知节点后插入 | $O(n)$(搬移) | $O(1)$ |
| 尾部插入 | $O(1)$ 均摊 | 有尾指针 $O(1)$,否则 $O(n)$ |
| 按值查找 | $O(n)$ | $O(n)$ |
| 缓存局部性 | 好 | 差(节点分散) |
三大心法¶
- 哑节点(dummy head):统一「空表」与「表头」的处理,避免大量
if分支 - 画图:每个指针操作前先画两三个节点的图,移动顺序错了就断链
- 快慢指针:用
fast每次 2 步、slow每次 1 步的「速度差」解决中点、判环、找入环点
§2 反转链表(LeetCode 206):迭代 + 递归¶
题目:反转整个链表。
迭代版公式(三指针)¶
设 $prev$ 为已反转段的新头方向、$cur$ 为当前节点、$nxt$ 为后继:
$$\text{loop:}\quad nxt \leftarrow cur.next,\quad cur.next \leftarrow prev,\quad prev \leftarrow cur,\quad cur \leftarrow nxt$$
关键:先保存 nxt 再改写 cur.next,否则链断。
递归版公式¶
$$f(head) = \begin{cases} head & head \text{ 为空或只剩一个节点} \\ f(head.next) \to \text{再接回} \ head & \text{否则} \end{cases}$$
即先反转后继子链,再让 head.next.next = head、head.next = None。
复杂度:时间 $O(n)$,空间迭代 $O(1)$ / 递归 $O(n)$(栈深)。
💡 反转链表的所有变体(反转区间、K 组翻转、回文链表)都建立在这 4 行迭代上。
✍️ §2.1 手算反转链表:1→2→3→4 四步指针走位¶
迭代反转三指针
prev / cur / nxt:保存nxt→ 反指cur.next=prev→ 整体前进——4 个节点手算。
设定:链表 1→2→3→4,初始 prev=None, cur=1。
| 步 | cur | nxt | cur.next← | 步后 prev | 步后 cur |
|---|---|---|---|---|---|
| 1 | 1 | 2 | None | 1 | 2 |
| 2 | 2 | 3 | 1 | 2 | 3 |
| 3 | 3 | 4 | 2 | 3 | 4 |
| 4 | 4 | None | 3 | 4 | None |
结束:prev=4 是新头,链表变为 4→3→2→1。
手算收获:
- 三句口诀:先存
nxt(否则改了cur.next就找不到后面的节点)、反指、前进——顺序错了就丢链(本 notebook §8 常见 bug) - 空间 $O(1)$:只用了 3 个指针,没开新数组——比"复制数组再反"省空间
- 递归版等价:
head.next反指当前节点(递归返回新头)——面试两种写法都要会(§2 代码) - 变体:K 个一组翻转(25)就是"分块做三次反转"——先会单链表反转,K 组是套壳
下面 numpy 复算。
# ---- §2.1 验证:numpy 复算反转链表 ----
class Node:
def __init__(self, v):
self.v, self.next = v, None
head = Node(1)
head.next = Node(2); head.next.next = Node(3); head.next.next.next = Node(4)
prev, cur = None, head
steps = 0
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
steps += 1
print(f'步{steps}: 当前反转段头 = {prev.v}')
assert steps == 4
vals = []
p = prev
while p:
vals.append(p.v)
p = p.next
print(f'反转结果 = {vals}')
assert vals == [4, 3, 2, 1]
print('\n✓ 与手算一致')
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】链表基础设施 + LeetCode 206 反转链表(迭代版与递归版两写法):
# 定义 ListNode、用数组建链 build、链表转数组 to_list,并实测两种反转。
# 【算法思路】迭代反转:三指针 prev / cur / nxt,每步「① 先保存后继 nxt=cur.next;② 反转指针
# cur.next=prev;③ 前进 prev=cur, cur=nxt」;循环结束后 prev 即新头。
# 递归反转:先递归反转后续子链表得到 new_head,再把 head.next.next 指回 head(成环指向),
# 最后 head.next = None 断开旧链接——本质是「后序遍历式」的重接线。
# 【变量含义】head=原链表头;prev=已反转部分的新头(初始 None);cur=当前待处理节点;
# nxt=cur 的后继(必须先保存,否则反转后丢失);new_head=递归版返回的新头;
# dummy=建链用的哑节点(统一处理空表);p=建链游标;res=转数组结果。
# 【循环不变量】迭代反转每轮结束后:prev 指向已反转完成的新头,cur 指向未反转部分的头;
# 递归反转中 reverse_list_recursive(head) 返回以 head 为起点的子链反转后的新头。
# 【关键边界】迭代版初始 prev=None(原头的 next 最终指向 None,成为新尾);
# while cur 循环条件(空链表 / 单节点天然成立);
# 递归版终止条件 head is None or head.next is None;
# 必须先保存 nxt 再改写 cur.next,否则丢后继造成环或断链。
# 【复杂度】两种反转均为时间 O(n)(每个节点处理一次);迭代版空间 O(1),递归版空间 O(n)(递归栈)。
# ════════════════════════════════════════════════════════════════════════
# 链表节点定义:val 存值,next 存下一个节点的引用
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 工具函数:用数组构造链表(哑节点避免头节点特判)
def build(arr):
dummy = ListNode() # 哑节点:统一处理空表
p = dummy # 当前指针,从哑节点出发
for x in arr: # 逐个元素创建节点并串联
p.next = ListNode(x)
p = p.next # 指针移到新节点
return dummy.next # 返回真正的头节点
# 工具函数:把链表转成数组(便于打印验证)
def to_list(head):
res = []
while head: # 遍历整个链表
res.append(head.val)
head = head.next # 指针后移
return res
def reverse_list(head):
prev = None
cur = head
while cur:
nxt = cur.next # 1. 先保存后继
cur.next = prev # 2. 反转指针
prev = cur # 3. 前进
cur = nxt
return prev
def reverse_list_recursive(head):
if head is None or head.next is None:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head # 后继的 next 指回自己
head.next = None
return new_head
print('迭代反转:', to_list(reverse_list(build([1, 2, 3, 4, 5])))) # 期望 [5,4,3,2,1]
print('递归反转:', to_list(reverse_list_recursive(build([1, 2, 3, 4, 5]))))
print('空表:', to_list(reverse_list(None))) # 期望 []
print('单节点:', to_list(reverse_list(build([1])))) # 期望 [1]
迭代反转: [5, 4, 3, 2, 1] 递归反转: [5, 4, 3, 2, 1] 空表: [] 单节点: [1]
§3 环形链表(LeetCode 141 / 142):Floyd 判圈推导¶
141 判断是否有环¶
快指针每次 2 步、慢指针每次 1 步。若存在环,快指针必然追上慢指针(速度差 1,环内距离有限)。
142 找入环节点(公式推导)¶
设:
- 头节点到环入口距离 $a$
- 环入口到相遇点距离 $b$
- 环长度 $L$
相遇时慢指针走了 $a + b$,快指针走了 $2(a+b)$,且快指针比慢指针多走了若干整圈:
$$2(a+b) = (a+b) + kL \implies a + b = kL \implies a = kL - b$$
即 从头节点出发走 $a$ 步,恰等于从相遇点再走 $kL - b$ 步(取模后即为环入口):
$$a \equiv L - b \pmod{L}$$
所以相遇后,让一个指针从头出发、另一个从相遇点出发,都每次走 1 步,再次相遇处就是环入口。
复杂度:时间 $O(n)$,空间 $O(1)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】Floyd 判圈算法两问:LeetCode 141 判断链表是否有环、LeetCode 142 找环入口节点,
# 并实现测试辅助函数 build_cycle(按数组建链、可选成环)。
# 【算法思路】141:快指针每次 2 步、慢指针每次 1 步。若有环,速度差 1 保证快指针绕环追上慢指针;
# 若快指针走到链尾(None)则无环。
# 142:设头到环入口 a、入口到相遇点 b、环长 L,相遇时慢指针走 a+b、快指针走 2(a+b),
# 于是 a+b = kL ⇒ a ≡ L-b (mod L)——因此相遇后再派一个指针从头出发,与相遇处的指针
# 同步每次 1 步,两者再次相遇的位置就是环入口。
# 【变量含义】arr=建链用的值数组;pos=-1 不成环,>=0 时尾节点指向第 pos 个节点成环;
# nodes=建链时收集的所有节点(成环用);dummy / p=建链辅助;
# slow / fast=快慢指针;p=142 中从头出发、寻找入口的指针。
# 【循环不变量】141 中 slow 每轮 +1、fast 每轮 +2,相对速度恒为 1;
# fast 不越界则必然与 slow 相遇(环内距离有限,每轮逼近 1)。
# 【关键边界】判环循环条件 while fast and fast.next(快指针访问 fast.next.next 前必须判空);
# 相遇判断用 slow is fast(引用比较,同一对象;不是 == 值比较);
# 142 中入口查找 while p is not slow,返回 p.val;无环返回 None。
# 【复杂度】时间 O(n)(快指针至多绕环一圈追上);空间 O(1)(只用了指针变量)。
# ════════════════════════════════════════════════════════════════════════
# 链表测试工具:按数组值建链,若 pos >= 0 则让尾节点指向第 pos 个节点形成环(供判圈题测试用)
def build_cycle(arr, pos):
# 构造链表并让尾节点指向第 pos 个节点(pos < 0 表示不成环)
dummy = ListNode()
p = dummy
nodes = [] # 记录每个节点,方便成环
for x in arr:
p.next = ListNode(x)
p = p.next
nodes.append(p)
if pos >= 0:
p.next = nodes[pos] # 尾节点指向第 pos 个节点,成环
return dummy.next
# 141. 判断链表是否有环:快慢指针,快指针每次 2 步、慢指针每次 1 步
def has_cycle(head):
slow = fast = head
while fast and fast.next: # 快指针能继续走才循环
slow = slow.next # 慢指针走 1 步
fast = fast.next.next # 快指针走 2 步
if slow is fast: # 相遇说明有环(速度差 1,必追上)
return True
return False # 快指针走到头 → 无环
# 142. 找环入口:相遇后一个指针从头出发、另一个从相遇点出发,同步走,再相遇即入口
def detect_cycle(head):
# Floyd:先找相遇点,再同步走找环入口
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head # 从头出发的指针
while p is not slow: # 两个指针各走 1 步,相遇处即环入口
p = p.next
slow = slow.next
return p.val # 返回入口节点的值
return None # 无环
print('有环:', has_cycle(build_cycle([3, 2, 0, -4], 1))) # 期望 True
print('无环:', has_cycle(build_cycle([1, 2], -1))) # 期望 False
print('入环节点值:', detect_cycle(build_cycle([3, 2, 0, -4], 1))) # 期望 2
print('入环节点值:', detect_cycle(build_cycle([1, 2], -1))) # 期望 None
有环: True 无环: False 入环节点值: 2 入环节点值: None
§4 合并有序链表 / 相交链表¶
题 3:合并两个有序链表(LeetCode 21,递归模板)¶
递推公式:
$$\text{merge}(l_1, l_2) = \begin{cases} l_2 & l_1 \text{ 为空} \\ l_1 & l_2 \text{ 为空} \\ l_1 \to \text{merge}(l_1.next, l_2) & l_1.val < l_2.val \\ l_2 \to \text{merge}(l_1, l_2.next) & \text{否则} \end{cases}$$
复杂度:时间 $O(n + m)$,空间 $O(n + m)$ 递归栈(迭代版 $O(1)$)。
题 4:相交链表(LeetCode 160,双指针公式)¶
思路:两个指针分别从 A、B 出发:走完自己链表后接上对方的链表继续走。
为什么正确:
$$\text{总步数}_A = len(A) + len(B) = \text{总步数}_B = len(B) + len(A)$$
两指针走过的总节点数相同 → 若有交点,必然在交点处同时到达(交点后路径完全重合);
若无交点,它们将同时到达各自链表末尾的 None。
复杂度:时间 $O(n + m)$,空间 $O(1)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 21 合并两个有序链表(递归模板)与 LeetCode 160 相交链表(双指针公式)。
# 【算法思路】21:递推 merge(l1, l2):一方为空返回另一方;否则取较小者作新头,
# 并让它指向「剩余部分」的合并结果(l1.next = merge(l1.next, l2),以此类推)——
# 递归地每次确定一个节点,天然稳定有序。
# 160:两个指针 pa / pb 分别从 A、B 出发,走完自己的链表后接上对方的链表继续走:
# 总步数相等(len(A)+len(B)),若有交点,两指针必在交点同时相遇(交点后路径重合);
# 若无交点,它们同时到达 None。
# 【变量含义】l1 / l2=两个有序链表头;pa / pb=160 的两个游走指针;
# head_a / head_b=两个链表头;common=相交部分头(测试构造用);
# a_head / b_head=手工构造的相交链表。
# 【递归终止 / 循环不变量】21 的递归终止:l1 或 l2 为空;
# 每层递归都假设 merge(l1.next, l2)(或对称)已经返回正确合并结果;
# 160 的循环不变量:任一时刻 pa 与 pb 距离「各自链表终点 + 对方链表」的剩余长度相等。
# 【关键边界】21:递归终止必须两个都判空;用 < 取较小者(相等时取 l1,保持稳定性不强制);
# 160:pa 走完切到 head_b、pb 走完切到 head_a(垫一步都不行,长度差无法弥补);
# 交点返回 pa.val、无交点返回 None(pa 为 None 时取 pa.val 会崩,需判空)。
# 【复杂度】21:时间 O(n+m)、空间 O(n+m)(递归栈,迭代版可 O(1));
# 160:时间 O(n+m)(两指针各走 n+m 步)、空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 21. 合并两个有序链表(递归模板):每次取较小的头,再接剩余部分的合并结果
def merge_two_lists(l1, l2):
if not l1: # l1 为空,直接返回 l2
return l2
if not l2: # l2 为空,直接返回 l1
return l1
if l1.val < l2.val: # 取较小者作为新头,递归合并剩余部分
l1.next = merge_two_lists(l1.next, l2)
return l1
else:
l2.next = merge_two_lists(l1, l2.next)
return l2
print('合并有序链表:', to_list(merge_two_lists(build([1, 2, 4]), build([1, 3, 4])))) # [1,1,2,3,4,4]
print('一方为空:', to_list(merge_two_lists(None, build([1])))) # [1]
def get_intersection_node(head_a, head_b):
# 走完自己再走对方:总步数相等,首次相遇即交点
pa, pb = head_a, head_b
while pa is not pb:
pa = pa.next if pa else head_b
pb = pb.next if pb else head_a
return pa.val if pa else None
# 构造相交链表:A = 1->2->3->4->5,B = 9->3->4->5,交点值为 3
common = build([3, 4, 5])
a_head = ListNode(1); a_head.next = ListNode(2); a_head.next.next = common
b_head = ListNode(9); b_head.next = common
print('相交节点值:', get_intersection_node(a_head, b_head)) # 期望 3
print('不相交:', get_intersection_node(build([1]), build([2]))) # 期望 None
合并有序链表: [1, 1, 2, 3, 4, 4] 一方为空: [1] 相交节点值: 3 不相交: None
§5 LRU 缓存(LeetCode 146):哈希 + 双向链表¶
题目:get / put 都 $O(1)$ 的最近最少使用缓存。
思路:
- 哈希表:键 → 节点,实现 $O(1)$ 查找
- 双向链表:头部是最新使用、尾部是最久未用,实现 $O(1)$ 移动与删除
- get 命中 → 节点移到头部;put 已存在 → 更新并移头部;超容量 → 淘汰尾部
为什么必须双向链表:删除尾部/移动节点都需要访问前驱,单向链表要 $O(n)$ 找前驱。
复杂度:get / put 均 $O(1)$,空间 $O(capacity)$。
💡 Python 面试直接写
OrderedDict即可(move_to_end + popitem),但要能讲清底层原理。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 146 LRU 缓存(OrderedDict 简版):get / put 均 O(1) 的最近最少使用缓存。
# Python 面试可直接写 OrderedDict(move_to_end + popitem),但要能讲清底层原理
# (底层即哈希表 + 双向链表,见下一个代码单元的「手写版」)。
# 【算法思路】OrderedDict 按插入顺序维护键值对:
# get 命中 → move_to_end(key) 把它标记为「最近使用」(移到队尾);
# put 已存在 → 先 move_to_end 再更新值;新增 → 直接写入(自然在队尾);
# 每次写入后若 len(d) > capacity,用 popitem(last=False) 淘汰队首(最久未用)。
# 【变量含义】capacity=缓存容量;d=OrderedDict(键→值,按访问序排列:队首最旧、队尾最新)。
# 【循环不变量】任何时刻 len(d) ≤ capacity;d 中键的顺序恒为「由旧到新」的访问顺序,
# 队首(popitem(last=False) 取出的)就是最久未用项。
# 【关键边界】get 未命中返回 -1(LRU 约定值);put 更新已有键时也要 move_to_end(更新即访问);
# 容量为 0 的缓存(capacity=0)put 后立即淘汰;
# 先 move_to_end 再赋值、最后才判断超容量淘汰(顺序保证刚访问的键不被误删)。
# 【复杂度】get / put 均摊 O(1)(OrderedDict 的 move_to_end / popitem 均为 O(1));空间 O(capacity)。
# ════════════════════════════════════════════════════════════════════════
# 146. LRU 缓存(OrderedDict 版):move_to_end 标记「最近使用」,popitem(last=False) 淘汰最久未用
from collections import OrderedDict
class LRUCache:
# OrderedDict:move_to_end 标记「最近使用」,popitem(last=False) 淘汰最久未用
def __init__(self, capacity: int):
self.capacity = capacity # 缓存容量
self.d = OrderedDict() # 有序字典:键值对按插入顺序排列
def get(self, key: int) -> int:
if key not in self.d: # 不存在返回 -1
return -1
self.d.move_to_end(key) # 命中 → 移到末尾表示最近使用
return self.d[key] # 返回值
def put(self, key: int, value: int) -> None:
if key in self.d:
self.d.move_to_end(key) # 已存在 → 先移到末尾(最近使用)
self.d[key] = value # 写入(更新或新增)
if len(self.d) > self.capacity:
self.d.popitem(last=False) # 超出容量 → 淘汰最久未用(队首)
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print('get(1) =', cache.get(1)) # 期望 1(1 变为最近使用)
cache.put(3, 3) # 淘汰最久未用的 2
print('get(2) =', cache.get(2)) # 期望 -1
print('get(3) =', cache.get(3)) # 期望 3
cache.put(4, 4) # 淘汰 1
print('get(1) =', cache.get(1)) # 期望 -1
print('get(4) =', cache.get(4)) # 期望 4
get(1) = 1 get(2) = -1 get(3) = 3 get(1) = -1 get(4) = 4
LRU 手写版:哈希表 + 双向链表(面试手撕核心)¶
为什么能 O(1)? 两个数据结构各管一件事:
- 哈希表
key -> 节点指针:O(1) 定位某个键对应的链表节点; - 双向链表:O(1) 增删节点(链表头 = 最近使用 MRU,链表尾 = 最久未用 LRU)。
get(key):哈希查不到 → 返回 -1;查到了 → 把该节点移到链表头(表示刚用过),返回 value。 put(key, value):已存在 → 更新 value 并移到链表头;不存在 → 头插新节点;插入后容量超限 → 删链表尾(最久未用)。
为什么必须双向链表而不是单向? 删除节点时需要把它前一个节点的 next 指向它的后一个——单向链表拿不到前驱,删除是 O(n);双向链表每个节点存 prev,O(1) 完成删除。这是面试追问的核心点。
实现技巧:用 head / tail 两个哨兵节点,头插、删尾都不必判空,代码更干净。
复杂度:get / put 均 O(1)(平均),空间 O(capacity)。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 146 LRU 缓存(面试手撕核心版):哈希表 + 双向链表,get / put 均摊 O(1)。
# 相比 OrderedDict 简版,这里完整展示 O(1) 的底层原理。
# 【算法思路】两个数据结构各管一件事:哈希表 cache(key → 节点)实现 O(1) 定位;
# 双向链表维护访问顺序(头 = 最近使用 MRU,尾 = 最久未用 LRU),实现 O(1) 增删;
# head / tail 两个哨兵节点使头插、删尾都免判空。
# get 命中 → _move_to_head 移到头;put 已存在 → 更新值并移头;新增 → 头插;
# 超容量 → _pop_tail 删尾并同步 del cache。
# 为什么必须双向链表:删除节点要把前驱的 next 指向它的后继——单向链表拿不到前驱 O(n),
# 双向链表每个节点存 prev,O(1) 完成删除(面试追问核心点)。
# 【变量含义】capacity=容量;cache=哈希表(key → DLinkedNode);
# head=哨兵头(head.next 即 MRU);tail=哨兵尾(tail.prev 即 LRU);
# node=DLinkedNode(含 key / value / prev / next);last=被淘汰的尾节点。
# 【循环不变量】链表始终形如 head ⇄ … ⇄ tail 双向环通(哨兵互联),节点总数 == len(cache);
# 越靠近 head 的节点越「新近被访问」,tail.prev 恒为最久未用。
# 【关键边界】_remove 用 node.prev.next = node.next 与 node.next.prev = node.prev 双向摘除;
# _add_to_head 四步顺序:node.prev=head → node.next=head.next → head.next.prev=node →
# head.next=node(顺序错会断链);put 新键后再查 len(cache) > capacity 决定是否淘汰;
# get 未命中返回 -1。
# 【复杂度】get / put 均摊 O(1)(哈希 O(1) + 链表 O(1));空间 O(capacity)。
# ════════════════════════════════════════════════════════════════════════
# 146. LRU 缓存(手写版):哈希表 O(1) 定位节点 + 双向链表维护访问顺序,get/put 均摊 O(1)
class DLinkedNode:
__slots__ = ('key', 'value', 'prev', 'next')
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
# 手写版:哈希 O(1) 定位节点 + 双向链表 O(1) 增删
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> DLinkedNode
self.head = DLinkedNode() # 哨兵头(其 next 是最近使用 MRU)
self.tail = DLinkedNode() # 哨兵尾(其 prev 是最久未用 LRU)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
"""从链表中摘除节点(O(1):删除必须知道前驱 → 所以用双向链表)"""
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
"""头插:插到哨兵 head 之后"""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _move_to_head(self, node):
self._remove(node)
self._add_to_head(node)
def _pop_tail(self):
"""删除最久未用(哨兵 tail 的前一个)"""
node = self.tail.prev
self._remove(node)
return node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_head(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._move_to_head(node)
return
node = DLinkedNode(key, value)
self.cache[key] = node
self._add_to_head(node) # 新键 → 头插
if len(self.cache) > self.capacity:
last = self._pop_tail() # 容量满 → 删链表尾
del self.cache[last.key]
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print('get(1) =', cache.get(1)) # 期望 1(1 移到链表头)
cache.put(3, 3) # 容量满,淘汰链表尾的 2
print('get(2) =', cache.get(2)) # 期望 -1
print('get(3) =', cache.get(3)) # 期望 3(3 移到链表头)
cache.put(4, 4) # 再次满,淘汰链表尾的 1
print('get(1) =', cache.get(1)) # 期望 -1
print('get(4) =', cache.get(4)) # 期望 4
get(1) = 1 get(2) = -1 get(3) = 3 get(1) = -1 get(4) = 4
§6 K 个一组翻转(25)/ 回文链表(234)¶
题 6:K 个一组翻转链表(LeetCode 25)¶
思路:哑节点 + 每轮三段式:
- 数:从
prev出发数 k 个节点,不足 k 个直接返回 - 翻:用双指针翻转
[start, tail]这一段(内部逻辑同反转链表) - 接:
prev.next = 新头、prev = 旧头(旧头成为新尾),再接下一组
复杂度:时间 $O(n)$(每组翻转 $O(k)$,共 $n/k$ 组),空间 $O(1)$。
题 7:回文链表(LeetCode 234)¶
思路三步:
- 快慢指针找中点(快指针 2 步 / 慢指针 1 步)
- 反转后半段
- 逐节点比较前半段与反转后的后半段
复杂度:时间 $O(n)$,空间 $O(1)$(不计算修改链表的临时空间)。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 25 K 个一组翻转链表 与 LeetCode 234 回文链表——链表题的进阶组合拳:
# 分段反转接线 + 快慢指针找中点。
# 【算法思路】25:哑节点 + 每轮三段式——① 数:从 prev 出发数 k 个节点(不足 k 个直接返回);
# ② 翻:用三指针把 [start, tail] 段就地反转(逻辑同 206);③ 接:prev.next=新头,
# prev 前进到旧头(新尾),再接下一组。
# 234:① 快慢指针找中点(快 2 步 / 慢 1 步,快到尾时慢在中点);② 从 slow 起反转后半段;
# ③ 双指针同步比较前半段与反转后的后半段,全部相等即回文。
# 【变量含义】head=链表头;k=每组长度;dummy=哑节点(统一出口与删头处理);prev=上一组尾(起点);
# tail=数出来的本组末尾;start=本组首节点;nxt_group=本组之后的首节点;
# cur / p / nxt=段内反转的三指针;slow / fast=快慢指针;left / right=回文比较指针。
# 【循环不变量】25:每轮开始时 prev 指向「上一组反转后的新尾」,组间接线完整;
# 234:反转结束后 prev 指向原后半段反转后的头,left 指向原头。
# 【关键边界】25:数 k 个时若 tail 中途变 None 立即返回 dummy.next(剩余不足 k 组保持原序);
# 段内反转循环 while cur is not nxt_group(把段尾指向组外首节点);
# 234:快慢指针循环 while fast and fast.next;比较循环 while right(右半短或等长);
# 空表 / 单节点直接为回文(循环自然通过)。
# 【复杂度】25:时间 O(n)(每组翻 O(k)、共 n/k 组)、空间 O(1);
# 234:时间 O(n)、空间 O(1)(不计原地修改链表的临时空间)。
# ════════════════════════════════════════════════════════════════════════
# 25. K 个一组翻转链表:按 k 分组,组内用三指针迭代反转,再与前后段重新接线
def reverse_k_group(head, k):
dummy = ListNode(0)
dummy.next = head
prev = dummy
while True:
# 1. 数 k 个,不足则返回
tail = prev
for _ in range(k):
tail = tail.next
if tail is None:
return dummy.next
start = prev.next # 本组第一个节点
nxt_group = tail.next # 本组后的第一个节点
# 2. 反转 [start, tail]
cur = start
p = nxt_group
while cur is not nxt_group:
nxt = cur.next
cur.next = p
p = cur
cur = nxt
# 3. 接回:prev.next = 新头(p),prev 前进到旧头(新尾)
prev.next = p
prev = start
print('k=2:', to_list(reverse_k_group(build([1, 2, 3, 4, 5]), 2))) # 期望 [2,1,4,3,5]
print('k=3:', to_list(reverse_k_group(build([1, 2, 3, 4, 5]), 3))) # 期望 [3,2,1,4,5]
print('k=1:', to_list(reverse_k_group(build([1, 2, 3]), 1))) # 期望 [1,2,3]
def is_palindrome(head):
# 1. 快慢指针找中点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. 反转后半段(从 slow 开始)
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# 3. 比较
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
print('回文偶数长:', is_palindrome(build([1, 2, 2, 1]))) # 期望 True
print('回文奇数长:', is_palindrome(build([1, 2, 3, 2, 1]))) # 期望 True
print('非回文:', is_palindrome(build([1, 2]))) # 期望 False
k=2: [2, 1, 4, 3, 5] k=3: [3, 2, 1, 4, 5] k=1: [1, 2, 3] 回文偶数长: True 回文奇数长: True 非回文: False
§7 复杂度总表(背熟)¶
| 题 | 时间 | 空间 | 核心技巧 |
|---|---|---|---|
| 反转链表 206 | $O(n)$ | $O(1)$ | 三指针迭代 |
| 环形链表 141/142 | $O(n)$ | $O(1)$ | Floyd 快慢指针 |
| 合并两个有序链表 21 | $O(n+m)$ | $O(n+m)$ 递归 | 递归/哑节点 |
| 相交链表 160 | $O(n+m)$ | $O(1)$ | 走完接对方 |
| LRU 146 | $O(1)$ | $O(cap)$ | 哈希 + 双向链表 |
| K 个一组翻转 25 | $O(n)$ | $O(1)$ | 哑节点 + 分段反转 |
| 回文链表 234 | $O(n)$ | $O(1)$ | 快慢 + 反转 |
哑节点技巧总结¶
$$\text{dummy} \to \text{head}$$
需要「返回新头」或「头节点可能被删除/修改」时(删除倒数第 N 个、K 组翻转、合并),用哑节点免除空表特判。
§8 常见 bug 与边界(面试踩坑区)¶
- 先保存后修改:
cur.next = ...前必须先存nxt,否则后继丢失 - 空指针解引用:
fast.next.next前必须判fast and fast.next - 循环条件:
head为 None 的遍历用while head:;判环用 while 快指针 - 递归爆栈:链表递归反转在 $n$ 很大时栈溢出,面试先写迭代版
- 没有哑节点:在头部插入/删除时特判写错导致断链
- 成环陷阱:测试用
to_list前确保链表无环,否则死循环 - 值比较 vs 引用比较:判环/相交用
is(同一对象),不是==(值相等) - K 组翻转的不足 k 组:剩余不足 k 个要保持原序不翻转(题 25 要求)
§9 面试追问与扩展(加分项)¶
9.1 手撕题:实现一个单链表 + 常用操作¶
- addAtHead / addAtTail / addAtIndex / deleteAtIndex(LeetCode 707)——哑节点写法
- 交换相邻节点(24)、反转区间(92)、分隔链表(86)、排序链表(148,归并)
9.2 为什么快慢指针能找中点¶
快指针速度是慢指针 2 倍 → 快指针到终点时慢指针恰好走了 $\lceil n/2 \rceil$ 步——即链表中间。速度差模式可以推广(如找倒数第 k 个:快指针先走 k 步)。
9.3 链表题通用调试法¶
- 小例子手推:画 3-4 个节点逐步走一遍
- 用「返回哑节点.next」统一出口,避免多个 return 分支不一致
- 涉及反转/拼接的题,先写 while 不变量注释(循环里什么不变)
§10 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 反转链表(LeetCode 206)
- 2. 环形链表(141)
- 3. 合并两个有序链表(21)
- 4. 删除链表的倒数第 N 个结点(19)
- 5. 链表的中间结点(876)
- 6. 相交链表(160)
- 7. 两数相加(2)
- 8. 移除链表元素(203)
- 9. 回文链表(234)
- 10. 删除排序链表中的重复元素(83)
L2 进阶(10 题)¶
- 11. LRU 缓存(146)
- 12. K 个一组翻转链表(25)
- 13. 环形链表 II(142)
- 14. 排序链表(148,归并)
- 15. 两两交换链表中的节点(24)
- 16. 反转链表 II(92)
- 17. 合并 K 个升序链表(23,堆)
- 18. 复制带随机指针的链表(138)
- 19. 分隔链表(86)
- 20. 设计链表(707)
L3 挑战(5 题)¶
- 21. LFU 缓存(460)
- 22. 合并 K 个排序链表最小堆版(23 的 O(n log k))
- 23. 二叉树展开为链表(114,树形链表)
- 24. 重排链表(143)
- 25. 奇偶链表(328)
自测要点¶
- 盲写:反转链表(迭代版)3 分钟内、Floyd 判圈 5 分钟内、LRU 用 OrderedDict 5 分钟内
- 讲清「为什么 LRU 需要双向链表」「为什么快慢指针相遇点能推出入环节点」
- 所有指针操作先讲「三指针顺序」,再写代码
§高频补充:删除链表倒数第 N 个结点(LeetCode 19)/ 两数相加(LeetCode 2)¶
19:哑节点 + 快慢指针——快指针先走 N 步,再与慢指针同步走,快指针到尾时慢指针恰好停在待删节点的前驱;哑节点统一处理「删头结点」。
2:模拟竖式加法,从低位到高位逐位相加,carry 记录进位;循环条件要带 carry,否则最后一位进位会丢。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 19 删除链表的倒数第 N 个结点:一趟遍历完成(不用先数长度),空间 O(1)。
# 【算法思路】哑节点 + 快慢指针:快指针先从哑节点出发走 n 步,然后快慢指针同步每次 1 步前进;
# 当快指针走到链尾(fast.next 为 None)时,慢指针恰好停在「待删节点的前驱」上,
# 用 slow.next = slow.next.next 跳过待删节点。哑节点统一处理「删除头结点」的边界。
# 【变量含义】head=链表头;n=倒数第几个(1 表示最后一个);dummy=哑节点(dummy.next 恒为结果头);
# fast=先走 n 步的指针;slow=最终停在待删节点前驱的指针。
# 【循环不变量】快慢指针同步阶段,两者间距恒为 n(快指针永远领先 n 个节点),
# 因此快指针到尾时,慢指针的 next 恰好指向倒数第 n 个节点。
# 【关键边界】快指针先走 n 步时 n 不超过链表长度(题目保证 n 有效);
# 同步循环用 while fast.next(判断的是快指针的下一位,慢指针因此停在待删前驱而非待删节点);
# 删除头结点场景:n == 链表长度时 slow 仍停在哑节点,slow.next.next 即原第二个节点——正确;
# 单节点删自己(n=1):dummy → node,快走 1 步到 node,fast.next 为 None,slow 在 dummy,
# slow.next = slow.next.next 置空,返回 dummy.next=None。
# 【复杂度】时间 O(n)(一趟);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 19. 删除链表的倒数第 N 个结点:哑节点 + 快慢指针,快指针先走 n 步,再同步前进直到快指针到末尾
def remove_nth_from_end(head, n):
# 哑节点 + 快慢指针:慢指针最终停在待删节点的前驱
dummy = ListNode(0, head) # 哑节点:统一处理删头结点
fast = slow = dummy
for _ in range(n): # 快指针先走 n 步
fast = fast.next
while fast.next: # 快慢同步走,快到尾时 slow 是前驱
fast = fast.next
slow = slow.next
slow.next = slow.next.next # 跳过待删节点
return dummy.next
print('删倒数第2个:', to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2))) # 期望 [1,2,3,5]
print('删头结点:', to_list(remove_nth_from_end(build([1, 2, 3]), 3))) # 期望 [2,3]
print('单节点删自己:', to_list(remove_nth_from_end(build([1]), 1))) # 期望 []
print('删最后一个:', to_list(remove_nth_from_end(build([1, 2]), 1))) # 期望 [1]
删倒数第2个: [1, 2, 3, 5] 删头结点: [2, 3] 单节点删自己: [] 删最后一个: [1]
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 2 两数相加:两个链表各代表一个整数(节点低位在前),求和并以链表返回。
# 模拟竖式加法的逐位相加 + 进位。
# 【算法思路】从两条链表头部(最低位)开始逐位相加:每轮 s = carry + l1.val(若有) + l2.val(若有),
# 当前位存 s % 10、进位 carry = s // 10,结果接到哑节点之后的链表上;
# 循环条件 while l1 or l2 or carry——最后一位的进位也不能漏。
# 【变量含义】l1 / l2=两个输入链表(游标随遍历前进);dummy=结果链表的哑节点;
# cur=结果链表当前尾节点;carry=进位(0 或 1);s=当前位置三位之和。
# 【循环不变量】已处理完的低位部分与输入的低位对齐、逐位正确相加,结果已链入 cur 之后;
# carry 恒等于已处理部分累计产生的进位。
# 【关键边界】循环条件必须带 or carry(如 9999 + 1:最高位产生最终进位 1,不带 carry 会丢);
# 两链长度不同:短的链耗尽后其 val 视为 0(if l1 / if l2 判空取 0);
# 结果节点存 s % 10(当前位),carry = s // 10(最多 1,因为 9+9+1=19);
# 返回 dummy.next(结果头)。
# 【复杂度】时间 O(max(len(l1), len(l2)));空间 O(max 长度)(结果链表本身,不计则 O(1) 辅助)。
# ════════════════════════════════════════════════════════════════════════
# 2. 两数相加:两个链表按低位对齐逐位相加,carry 记录进位,结果同样用链表返回
def add_two_numbers(l1, l2):
# 链表模拟加法:低位对齐逐位相加,carry 处理进位
dummy = ListNode(0)
cur = dummy
carry = 0
while l1 or l2 or carry: # 最后一位进位也不能漏
s = carry
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
cur.next = ListNode(s % 10)
cur = cur.next
carry = s // 10
return dummy.next
print('342+465:', to_list(add_two_numbers(build([2, 4, 3]), build([5, 6, 4])))) # 期望 [7,0,8]
print('0+0:', to_list(add_two_numbers(build([0]), build([0])))) # 期望 [0]
print('9999+1:', to_list(add_two_numbers(build([9, 9, 9, 9]), build([1])))) # 期望 [0,0,0,0,1] 进位
print('长度不同:', to_list(add_two_numbers(build([1, 8]), build([0])))) # 期望 [1,8]
342+465: [7, 0, 8] 0+0: [0] 9999+1: [0, 0, 0, 0, 1] 长度不同: [1, 8]