408 算法拓展训练：考纲内的经典题

Intro

「从暴力解到最优解」真题专题把 2009–2026 年 408 数据结构的算法设计题讲完了，一共 22 道。真题就这么多，练完就没了——但那套「先写对暴力解、再判断要不要优化、需要时找出浪费」的方法，值得用更多题目继续练。

本模块是沿着该思路解决这个问题：

• 主要内容：从 408 数据结构考纲范围内精选的经典算法设计题——KMP、链表判环、判断平衡二叉树、由遍历序列构造二叉树、拓扑排序判环……这些都是大纲明确覆盖的知识点，只是真题的代码大题还没有直接考过。它们是练方法论的好载体。
• 和真题的关系。这些题来自教材和机试里反复出现的经典题型，用来练手、补考点空白，但它们没有真题的地位。
• 能压题么？。选这些题的唯一理由是「考纲内 + 经典 + 能练那套判断力」，不是「预测明年会考」。其实内容就这么多，再继续看更多的其实roi很低。

题目价值

真题的算法设计题分布并不均匀：链表、数组、树、图、排序都考过，但串（KMP）的代码题一次没考过，二叉树里「判平衡」「构造」这类高频操作也没进过大题。真题的空白，恰恰是拓展训练的价值所在——它把方法论覆盖到真题够不着的考点上。

更重要的是，这些题和真题共享同一批优化手段：链表判环用的快慢指针，是 2009·42 的兄弟；判断平衡二叉树的「自底向上一遍算完」，和真题里「消除重复计算」是同一招；KMP 消除的「模式串回退时主串指针也跟着退」的浪费，本质和数组题里「重复扫描」是一回事。练拓展题，就是把真题里学到的手段，迁移到新场景里再打一遍。

学习思路

每一篇的结构和真题专题完全一样，分两类：

• 暴力→最优型：先写对暴力解、按判分口径估分、找出浪费、升级成最优解，两版代码可视化对照。用于有真实分差的题（判环、回文、判平衡、KMP、二分边界、逆序对……）。
• 直观即满分型：直观写法就是最优解，重点在「为什么不用优化」和「别画蛇添足」。用于遍历/统计即达下界的题（合并链表、括号匹配、二叉树遍历应用、连通分量……）。

建议先练真题专题、把两套模板的手感建立起来，再用这个系列扩大练习面。

拓展题目录（按章节）

一、线性表

• 单链表判环：从哈希表到快慢指针（暴力→最优）
• 判断链表回文：从复制到数组到中点逆置（暴力→最优）
• 合并两个有序链表：直白拼接即满分（直观即满分）
• 删除排序链表的重复元素：一趟相邻比较（直观即满分）
• 顺序表原地删除指定元素：双指针一趟搬移（直观即满分）

二、栈、队列和数组

• 括号匹配：一个栈走一遍（直观即满分）
• 逆波兰（后缀）表达式求值：栈上直接算（直观即满分）
• 中缀表达式转后缀：栈处理优先级（直观即满分）
• 用栈实现队列：两个栈的分工（设计题）

三、串

• KMP 模式匹配：从朴素回退到 next 数组（暴力→最优）

四、树与二叉树

• 二叉树的最大深度：一遍递归即满分（直观即满分）
• 判断平衡二叉树：从自顶向下到自底向上（暴力→最优）
• 判断对称二叉树：镜像同步遍历（直观即满分）
• 由先序和中序序列构造二叉树：递归定位根（直观即满分）
• 判断完全二叉树：层序遍历一遍（直观即满分）
• 中序遍历的非递归写法：用栈模拟递归（设计题）
• 翻转二叉树：一遍遍历交换左右（直观即满分）

五、图

• 连通分量计数：DFS 数一遍（直观即满分）
• 课程表·拓扑排序判环：Kahn 摘点（直观即满分）
• 判断无向图是否为树：连通且无环（暴力→最优）

六、查找与排序

• 二分查找左右边界：从线性扫到二分收敛（暴力→最优）
• 求逆序对数：从双重循环到归并顺带统计（暴力→最优）

这里看完，再投入精力到代码里其实边际效益就很低了，如果真的不过瘾，可以来https://www.codebrick.tech/algo-blog/ 对掏