0. 重点算法汇总

ABSTRACT · 定位本页是数据结构代码题的总入口，逐页覆盖原 PDF 的 30 页：顺序表、链表、栈与队列、二叉树、查找、图和排序。原 PDF 只有文字与代码，没有独立知识图；正文用可编辑 Mermaid 图补充导航。

IMPORTANT · 唯一权威代码汇总页保留每个原算法的核心不变量、边界、复杂度和专题深链接，不再复制同一份 C++。完整实现只维护在 1～7 篇专题笔记中，避免“专题代码已修正、汇总代码仍旧错误”的双份漂移。七篇现有 97 个 C++17 代码块，并已分别通过 7 套可执行测试。

flowchart LR
    H[重点算法汇总] --> A[顺序表]
    H --> L[链表]
    H --> S[栈与队列]
    H --> T[二叉树]
    H --> F[查找]
    H --> G[图]
    H --> O[排序]
    A --> I1[下标与写指针]
    L --> I2[前驱与断链重连]
    S --> I3[栈顶与队头边界]
    T --> I4[递归出口与回溯]
    F --> I5[区间与全局约束]
    G --> I6[访问标记与方向]
    O --> I7[有序区与稳定性]

1. 专题入口与验证状态

专题	原资料范围	权威笔记	当前验证
顺序表	逆置、删除、去重、合并、中位数、最小未出现正整数	顺序表专题	11 页，14 个代码块，断言通过
链表	删除、逆置、拆分、合并、公共元素、倒数第 $k$ 个、对称、重排	链表专题	24 页，25 个代码块，断言通过
栈与队列	队列逆置、中心对称、括号匹配	栈与队列专题	6 页，7 个代码块，断言通过
二叉树	递归统计、查找、路径、构造、层次遍历、完全性、线索化	二叉树专题	30 页，23 个代码块，断言通过
查找	有序表查找/插入、折半、BST 判断与操作	查找专题	7 页，8 个代码块，断言通过
图	存储、BFS/DFS、最短路、可达性、判树、连通分量、转换	图专题	13 页，12 个代码块，断言通过
排序	插入、冒泡、快速、选择、堆、归并	排序专题	8 页，8 个代码块，断言通过

2. 顺序表与虚拟数组

原 PDF 算法	核心不变量	边界与复杂度	权威入口
原地逆置	左右下标向中间收缩，每次交换一对	空表、单元素均不交换；$O(n)$ 时间、$O(1)$ 空间	原地逆置
删除指定值或区间	读下标扫描原表，写下标始终指向下一个保留位置	写指针只在保留时前进；$O(n)$、$O(1)$	删除指定值、删除区间
递增表去重	`write` 指向最后一个已保留的不同值	依赖“原表有序”；空表单独处理；$O(n)$、$O(1)$	有序表去重
合并两个递增表	两个读指针指向各自未处理首元，写指针指向输出尾	输出容量至少 $m+n$；$O(m+n)$	递增表合并
两递增序列中位数	只需归并到合并序列目标下标，不必复制全部结果	先明确总长度奇偶与题目采用的中位数口径；$O(m+n)$ 上界	合并中位数
最小未出现正整数	长度为 $n$ 时答案只可能位于 $[1,n+1]$，记录 $1..n$ 是否出现	忽略非正数和大于 $n$ 的数；$O(n)$ 时间、$O(n)$ 空间	最小缺失正整数

TIP · 专题页补充题型有序插入、末元素覆盖最小值、交换连续子序列和Boyer-Moore 主元素也已纳入专题笔记。

DANGER · 原汇总代码的代表性错误去重时覆盖位置和 length 少 1；合并函数混用 l/l3 且漏分号；虚拟数组写成 int record = new int[n]，返回时又使用未定义的 maxNumber。以上均不能直接编译，专题版本已按空表、容量和下标边界重写。

3. 链表

链表题的通用动作是：先保存后继，再断链或重连；释放结点后绝不再访问；带头结点与无头链表不能混用同一套首结点处理。

原 PDF 算法	核心不变量与边界	复杂度	权威入口
递归删除无头链表中所有 `x`	头指针必须按引用传递；命中首结点后更新头再递归	$O(n)$ 时间，$O(n)$ 递归栈	递归删除
非递归删除带头链表中所有 `x`	`previous` 指向待检查结点前驱；删除后不前移前驱	$O(n)$、$O(1)$	非递归删除
删除唯一最小结点	扫描并保存最小结点的前驱，最后统一摘链释放	$O(n)$、$O(1)$	删除最小结点
递增链表去重	只比较相邻结点；删除重复者后当前基准不前移	$O(n)$、$O(1)$	链表去重
原地逆置	保存 `next`，把当前结点头插到已逆置区	$O(n)$、$O(1)$	单链表逆置
按奇偶位置稳定拆分	两条尾指针分别接收奇位、偶位结点，结尾都置空	$O(n)$、$O(1)$	稳定拆分
奇位正序、偶位逆序拆分	奇位尾插，偶位头插；每次先保存下一结点	$O(n)$、$O(1)$	正逆序拆分
两递增链表合并为非递减链表	尾指针接较小原结点；相等时选择顺序决定稳定口径	$O(m+n)$、$O(1)$	递增链合并
公共元素生成新链 `C`	两指针比较：相等则复制并双双前进，否则较小者前进	$O(m+n)$，另需结果空间	公共元素
倒数第 $k$ 个结点	快指针先走 $k$ 步，再与慢指针同步前进	$k\ge1$ 且长度不少于 $k$；$O(n)$	倒数第 k 个
循环双链表对称	首尾指针相向移动；奇偶长度分别在相遇或交叉时停止	$O(n)$、$O(1)$	循环双链表对称
重排为 $a_1,a_n,a_2,a_{n-1},\ldots$	快慢指针分半、逆置后半、两链交替合并	$O(n)$、$O(1)$	链表重排

DANGER · 原汇总代码的代表性错误递归删除按值传递头指针；非递归删除无条件前移前驱而跳过连续 x；空指针检查写在解引用之后；new LNode* 把“结点”误写成“指针对象”；循环双链表向左移动却写成 q = q->next。专题页已统一内存所有权、头结点约定和循环终止条件。

4. 栈与队列

原 PDF 算法	核心不变量与边界	复杂度	权威入口
用空栈逆置队列	所有队列元素依次入栈，再全部出栈回队；必须检查容量	$O(n)$ 时间、$O(n)$ 栈空间	队列逆置
判断带头单链表是否中心对称	前半段入栈；奇数长度跳过中点；后半段与栈逆序比较	$O(n)$ 时间、$O(n)$ 空间	中心对称
圆括号匹配	左括号入栈；右括号到来时栈不得空；扫描结束栈必须空	$O(n)$ 时间、$O(n)$ 空间	括号匹配

TIP · 专题页补充题型共享栈补全了两栈判满、判空、入栈与出栈；字符序列重排补全了按字符类别分区题型。该实现会逆转 H 组；只有字符完全相同时逆序才不可见，不能称为一般意义上的稳定分区。

DANGER · 原汇总代码的代表性错误队列与栈对象、指针访问方式混用，front/rear/top 有时漏写所属对象；括号匹配在空栈上直接 pop，结尾真假分支相反且包含连续两个 return。

5. 二叉树

树递归先写空树出口，再明确“本结点贡献”和“左右子树结果如何组合”。根位于第 1 层；WPL 的根路径长度按边数记为 0。

原 PDF 算法组	关键条件与易错边界	权威入口
统计结点总数、双分支结点数、树高	空树分别返回 0；双分支要求左右孩子均非空；高度为两侧最大值加 1	递归统计
表达式树求值	叶结点返回操作数；内部结点必须有两个孩子并按运算符组合	表达式树
判断结构相似、镜像二叉树	两空相似、一空一非空不相似；镜像须交换每个结点的左右子树，既可先递归后交换，也可先交换再分别递归两棵新子树	结构相似、镜像
查找值为 `key` 的结点与层号	返回指针或层号必须向上传播“已找到”状态，不能找到后继续覆盖	查找与层号
叶结点串链、输出根到叶路径	`head/tail` 必须按引用更新；路径进入压栈、每个分支返回时都回溯弹栈	叶链表、根到叶路径
叶结点带权路径长度 WPL	只在叶结点累计 $w\times d$，根深度为 0；兄弟分支深度不能互相污染	WPL
满二叉树先序转后序	仅适用于各层全满、结点数为 $2^h-1$ 的完美二叉树，左右子树才可等分	先序转后序
先序 + 中序重建	关键字互异时唯一；先序首元定位中序根，左段长度决定两边递归范围	遍历序列重建
顺序存储转链式二叉树	0 下标孩子为 $2i+1,2i+2$；普通树数组必须显式保留空位置	顺序存储建树
层次遍历与完全性	队列保存待访问结点；判完全树时首个空位置之后不得再出现非空结点	层次遍历、完全二叉树
中序线索化	当前无左孩子才设前驱线索；应检查“前驱无右孩子”后给前驱设后继线索	中序线索化

除由先序/中序重建在直接线性定位根时最坏为 $O(n^2)$ 外，上述遍历、统计、查找和转换通常都访问每个结点一次，为 $O(n)$；递归辅助空间为 $O(h)$，层次遍历为 $O(w)$。

DANGER · 原汇总代码的代表性错误多处左右递归写成两次左子树；深度与 WPL 递归进入子树后未正确恢复；表达式树使用未声明的 p；查找结果按值传递；叶链表 head/tail 按值传递；顺序建树把右孩子再次赋给左孩子；完整树空树判断写成 bt == true；线索化检查的是当前结点右孩子而不是前驱右孩子。

6. 查找

原 PDF 算法	核心不变量与边界	复杂度	权威入口
递增顺序表查找：找到则与后继交换，否则插入	折半区间统一为半开区间 `[low, high)`；未找到时 `low` 就是插入位置；末元素命中时没有后继可换。若命中后与更大的后继交换，表不再有序，不能不经重排就再次折半查找	查找 $O(\log n)$，插入移动 $O(n)$	查找后交换或插入
BST 最大值	非空树沿真实右孩子走到底；空树没有合法最大值，不能用 0 冒充	$O(h)$	BST 最值

TIP · 专题页补充题型专题还覆盖链表命中后与前驱交换、两种折半查找、BST 全局范围验证、BST 层次和中序范围输出。

DANGER · 原汇总代码的代表性错误折半查找把 high = mid - 1 放到循环外，插入移动时混用 list.data 与 list[]，还未检查容量；BST 空树直接返回 0 会把“无结果”和合法关键字 0 混为一谈。

7. 图

原 PDF 算法组	核心不变量与边界	权威入口
邻接表、邻接矩阵与无向边插入	无向边在邻接表存两条邻接记录，但逻辑边数只加 1；自环度数贡献 2	图存储
BFS	顶点首次发现、准备入队时立即标记，保证最多入队一次	BFS
BFS 求无权最短路	`distance[source]=0`，未发现为 -1；首次发现邻点时距离加 1	无权最短路
递归 DFS 与可达性	进入结点立即标记；有向图必须按弧方向判断，不能假设可达对称	DFS、可达性
无向图判树	非空、无向、连通且 $\lvert E\rvert=\lvert V\rvert-1$；单顶点无边图是树	无向图判树
无向图连通分量	每从一个未访问顶点启动一次 DFS，就完整覆盖一个新分量	连通分量

邻接表上的 BFS、DFS、可达性、判树与连通分量均为 $O(|V|+|E|)$；邻接矩阵遍历通常为 $O(|V|^2)$。

TIP · 专题页补充题型欧拉通路补全了非零度顶点连通性与奇度条件；最远顶点规定了同层平局；非递归 DFS保存下一邻接位置；存储转换处理方向、自环、重边和边数一致性。

DANGER · 原汇总代码的代表性错误类型在使用后才声明，new AGraph*/new ArcNode* 分配了错误对象，成员访问混用 . 与 ->；BFS 初始化在循环外，队列前置自增易错；DFS 混用 p.adjVertex、visit[] 和未声明变量；可达性分支含不可达 return；连通分量调用未定义的 v。

8. 排序

原汇总 PDF 只重复了直接插入与快速排序，完整排序族以排序专题为准。

算法	最好时间	平均/最坏时间	空间与稳定性	权威入口
直接插入	$\Theta(n)$	$\Theta(n^2)$	$\Theta(1)$，稳定	直接插入
折半插入	$\Theta(n\log n)$	平均/最坏 $\Theta(n^2)$	$\Theta(1)$，稳定	折半插入
优化冒泡	$\Theta(n)$	$\Theta(n^2)$	$\Theta(1)$，稳定	冒泡
快速排序	$\Theta(n\log n)$	平均 $\Theta(n\log n)$，最坏 $\Theta(n^2)$	平均栈 $O(\log n)$，不稳定	快速排序
简单选择	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$，不稳定	简单选择
堆排序	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(1)$，不稳定	堆排序
二路归并	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n)$，稳定	归并排序

DANGER · 原汇总代码的代表性错误直接插入在 j 离开作用域后继续使用，并把哨兵写回成 R[j] 而非 R[0]；快排使用严格不等号，重复关键字可能使双指针停滞，递归调用又被错误放到了函数花括号之外。

9. 30 页逐页覆盖记录

页码	原 PDF 内容	复核去向
1～3	顺序表逆置、删除、去重、合并、中位数、虚拟数组	本文第 2 节 + 顺序表专题
4～10	链表删除、最小值、去重、逆置、拆分、合并、交集、倒数第 $k$ 个、循环双链表、重排	本文第 3 节 + 链表专题
11～12	栈/队列结构、队列逆置、中心对称思路、括号匹配	本文第 4 节 + 栈与队列专题
13～24	二叉树递归统计、表达式、相似/镜像、查找、叶链表、路径、WPL、构造、层次遍历、完全性	本文第 5 节 + 二叉树专题
25	中序线索化与有序顺序表查找/插入	本文第 5、6 节
26	BST 最大值与图的存储结构	本文第 6、7 节
27～28	无向边插入、BFS、无权最短路、DFS、可达性	本文第 7 节 + 图专题
29	图判树、连通分量、直接插入排序	本文第 7、8 节
30	快速排序	本文第 8 节 + 排序专题

SUCCESS · 完整性结论 30 页中的每个算法项都已在本页建立检索项并指向权威专题；水印、错位花括号、未声明变量和不可编译旧代码没有带入正式笔记。没有独立知识图被遗漏。

10. 代码题统一检查清单

结构约定：是否带头结点、是否循环、数组从 0 还是 1 开始、图是有向还是无向。
空与单元素：空表、空树、单结点、无边图分别返回什么，是否允许空答案。
指针所有权：改变头指针或输出指针时是否按引用传递；new/delete 与 malloc/free 不混用。
保存下一位置：覆盖数组元素、摘链、释放结点、移动图邻接指针之前，先保存仍需使用的位置。
标记时机：BFS/DFS 在首次发现结点时标记，避免重复入队、入栈或递归。
递归状态：空结构出口、左右递归方向、返回值传播、路径/深度回溯是否全部正确。
数学前提：BST 的全局范围、欧拉路的连通性、完全树的连续位置、排序稳定性的相等元素处理。
复杂度：区分总时间、关键字比较、元素移动、递归栈和结果空间；写明最坏退化条件。
验证输入：至少覆盖空、单元素、重复值、负数、已有序、逆序、断连与非法边界。

11. 本节复盘

顺序表题抓“读指针/写指针”和容量；链表题抓“前驱、后继、断链、重连、所有权”。
栈队列题先画清栈顶和队头队尾含义；括号匹配同时检查提前右括号和最终剩余左括号。
二叉树递归统一为“空树出口 + 当前贡献 + 左右结果”，路径与深度状态必须在回溯时恢复。
查找题统一折半区间并写明失败后的插入点；BST 递归必须传递全局上下界。
图遍历在首次发现时标记；无向判树、欧拉路和连通分量都必须明确连通条件。
排序先写下标体系、有序区边界和稳定性；快排重复值、堆孩子越界、归并剩余段是高频错误。
汇总页负责导航和审查，专题页负责唯一可编译实现；修改算法时只更新专题权威代码，再回查本页链接与口径。