黑马数据结构讲义
基础数据结构-051-递归-尾调用与尾递归
课程文档整理：尾调用与尾递归优化
一、核心概念解析
- 尾调用（Tail Call）
定义
在函数中，若最后一步操作是调用另一个函数（且无需执行后续操作），则称为尾调用。
示例代码
function A() {
...
return B(); // 最后一步直接调用函数B
}反例说明
• 案例1：非尾调用（返回操作）
function A() {
const result = B();
return result; // 最后一步是返回而非直接调用
}• 案例2：非尾调用（附加运算）
function A() {
return B() + 1; // 最后一步是加法运算
}• 案例3：非尾调用（运算后返回）
function A() {
return B() + C(); // 最后一步是复合运算
}- 尾递归（Tail Recursion）
定义
当函数在最后一步调用自身时，称为尾递归，属于尾调用的特殊形式。
二、编译器优化机制
- 传统调用栈分析
graph TD
A[A调用] --> B[B调用]
B --> C[C调用]
C --> D[返回结果]• 问题：嵌套调用时，外层函数需等待内层函数完全执行，导致内存无法释放
- 尾调用优化（TCO）
优化效果
graph TD
A[A调用] -->|释放A内存| B[B调用]
B -->|释放B内存| C[C调用]
C --> D[直接返回结果]• 优势：
• 栈帧复用（Stack Frame Reuse）
• 内存占用恒定（O(1)）
• 避免栈溢出风险
实现条件
- 调用必须是函数执行的最后一步
- 调用结果直接作为当前函数的返回值
- 语言/运行时环境支持（如ES6、Scheme等）
三、技术原理深度解析
- 可优化原因
• 上下文无关性：被调用函数无需访问调用者的上下文环境
• 结果传递性：直接传递最终结果，无需中间处理
- 限制条件
• 非尾调用场景：
function A() {
return B() + process(); // 需执行process()运算
}• 闭包依赖：当存在闭包引用时无法优化
四、语言支持情况
- 完全支持
• Scheme（规范强制要求）
• Lua
• ES6（严格模式下）
- 部分支持
• C/C++（编译器可选优化）
• Java（JVM限制，但Scala等JVM语言支持）
- 不支持
• Python（明确放弃支持）
• Ruby（MRI不支持）
五、教学案例演示
- 递归优化对比
未优化版本
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1); // 非尾递归
}尾递归版本
function factorial(n, acc = 1) {
if (n === 1) return acc;
return factorial(n - 1, n * acc); // 尾递归形式
}六、扩展学习建议
- 浏览器调试工具栈跟踪对比
- 函数式编程范式中的核心应用
- WebAssembly中的实现差异
- 尾递归与循环结构的性能对比
（文档已修正原始录音中的术语错误，规范技术表述，确保概念准确性。代码示例采用标准JavaScript语法，便于理解核心原理）
基础数据结构-052-递归-尾递归避免爆栈
Scala尾递归优化课程文档
目录
- Scala语言简介
- 开发环境搭建
- 基础语法入门
- 递归与尾递归优化
- 递归改循环方案
- Scala语言简介
• JVM系语言，编译为.class文件
• 与Java高度兼容，支持混合编程
• 函数式编程特性
• 支持尾递归优化（Tail Recursion Optimization）
- 开发环境搭建
2.1 IntelliJ插件安装 - 打开Settings → Plugins
- 搜索安装"Scala"插件
- 重启IDE生效
2.2 项目创建
- New Project → Language选择"Scala"
- 构建工具选择SBT（类似Maven）
- 标准目录结构：
src/ main/ scala/ // Scala源码目录 java/ // Java源码目录 test/
- 基础语法入门
3.1 Hello World示例
object Main {
def main(args: Array[String]): Unit = {
println("Hello Scala")
}
}3.2 语法要点
• object：单例对象声明
• def：方法定义关键字
• 参数格式：参数名: 类型
• Unit：等价Java的void
• 行尾分号可省略
- 尾递归优化实践
4.1 普通递归问题
def sum(n: Long): Long = {
if (n == 1) 1
else n + sum(n - 1)
}问题：Stack Overflow（n=15000时）
4.2 尾递归优化实现
import scala.annotation.tailrec
def sum(n: Long): Long = {
@tailrec
def loop(current: Long, acc: Long): Long = {
if (current == 1) acc + 1
else loop(current - 1, acc + current)
}
loop(n, 0)
}4.3 优化原理
- 尾递归特征：函数最后操作仅为自身调用
- 编译器优化：复用栈帧，避免堆栈溢出
- 必须使用
@tailrec注解验证
4.4 执行过程分析（以sum(3)为例）
| 调用层次 | current | acc | 操作 |
|---|---|---|---|
| 1 | 3 | 0 | loop(2, 3) |
| 2 | 2 | 3 | loop(1, 5) |
| 3 | 1 | 5 | 返回5+1=6 |
- 递归改循环方案
5.1 通用解决方案
def sumByLoop(n: Long): Long = {
var result = 0L
for (i <- n to 1 by -1) {
result += i
}
result
}5.2 递归使用建议
优先考虑循环实现
必须使用递归时：
• 保持尾递归形式• 添加
@tailrec验证• 控制递归深度
附录：开发注意事项
- SBT依赖管理需配置
build.sbt - 混合开发时注意Scala/Java互操作
- 推荐IDE插件：Scala插件、SBT工具
- 调试工具：JVM Debugger通用
提示：所有支持尾递归优化的语言都会严格验证尾调用形式，非尾递归形式无法获得优化效果。
基础数据结构-053-递归-主定理求时间复杂度-1
递归时间复杂度计算与主定理应用详解
目录
- 主定理概述
- 主定理公式与参数说明
- 主定理的三种情况
- 六道典型例题解析
- 应用总结
一、主定理概述
主定理（Master Theorem）是计算递归算法时间复杂度的核心工具，适用于满足特定形式的递归关系式。通过主定理可快速判断时间复杂度，无需展开递归树或进行复杂推导。
二、主定理公式与参数说明
- 递归关系式形式
[ T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) ]
• T(n)：问题规模为 n 的总运行时间
• a：子问题的个数（拆分后的递归调用次数）
• b：每次递归时问题规模的缩小倍数（子问题规模为原问题的 (1/b)）
• f(n)：递归外其他操作的时间复杂度
- 关键参数计算
计算对数参数 ( x = \log_b a )，即求解方程 ( b^x = a )。
三、主定理的三种情况
根据 ( x ) 与 ( f(n) = \Theta(n^c) ) 中 ( c ) 的关系，时间复杂度分为三种情况：
| 情况 | 条件 | 时间复杂度 |
|---|---|---|
| Case 1 | ( x > c ) | ( \Theta(n^x) ) |
| Case 2 | ( x = c ) | ( \Theta(n^c \log n) ) |
| Case 3 | ( x < c ) | ( \Theta(n^c) ) |
四、六道典型例题解析
例题 1：( T(n) = 2T\left(\frac{n}{2}\right) + n^4 )
• 参数：( a=2, b=2, f(n)=n^4 )
• 计算：( x = \log_2 2 = 1 )，( c=4 )
• 判断：( x=1 < c=4 ) → Case 3
• 结果：( \Theta(n^4) )
例题 2：( T(n) = T\left(\frac{7n}{10}\right) + n )
• 参数：( a=1, b=10/7, f(n)=n )
• 计算：( x = \log_{10/7} 1 = 0 )，( c=1 )
• 判断：( x=0 < c=1 ) → Case 3
• 结果：( \Theta(n) )
例题 3：( T(n) = 16T\left(\frac{n}{4}\right) + n^2 )
• 参数：( a=16, b=4, f(n)=n^2 )
• 计算：( x = \log_4 16 = 2 )，( c=2 )
• 判断：( x=2 = c=2 ) → Case 2
• 结果：( \Theta(n^2 \log n) )
例题 4：( T(n) = 7T\left(\frac{n}{3}\right) + n^2 )
• 参数：( a=7, b=3, f(n)=n^2 )
• 计算：( x = \log_3 7 \approx 1.77 )，( c=2 )
• 判断：( x \approx 1.77 < c=2 ) → Case 3
• 结果：( \Theta(n^2) )
例题 5：( T(n) = 7T\left(\frac{n}{2}\right) + n^2 )
• 参数：( a=7, b=2, f(n)=n^2 )
• 计算：( x = \log_2 7 \approx 2.81 )，( c=2 )
• 判断：( x \approx 2.81 > c=2 ) → Case 1
• 结果：( \Theta(n^{\log_2 7}) )
例题 6：( T(n) = 2T\left(\frac{n}{4}\right) + \sqrt{n} )
• 参数：( a=2, b=4, f(n)=\sqrt{n} )
• 计算：( x = \log_4 2 = 0.5 )，( c=0.5 )
• 判断：( x=0.5 = c=0.5 ) → Case 2
• 结果：( \Theta(\sqrt{n} \log n) )
五、应用总结
- 识别递归形式：确认 ( T(n) = aT(n/b) + f(n) ) 的结构。
- 计算关键参数：确定 ( a, b, f(n) )，计算 ( x = \log_b a )。
- 比较 ( x ) 与 ( c )：明确属于主定理的哪种情况。
- 注意例外情况：若递归式不满足主定理条件，需使用递归树或代入法求解。
通过掌握主定理，可高效解决大部分递归算法的时间复杂度分析问题。
基础数据结构-054-递归-主定理求时间复杂度-2
主定理在递归算法中的应用案例详解
目录
- 递归版二分查找的主定理分析
- 归并排序的时间复杂度推导
- 快速排序的时间复杂度讨论
- 递归版二分查找的主定理分析
算法特征分析
• 子问题个数 (a)：每次递归仅执行一个分支（if/else if），故 a = 1
• 规模缩减倍数 (b)：每次将数据规模对半分割，b = 2
• 非递归操作复杂度 (f(n))：仅包含比较运算和位移操作，时间复杂度为 O(1)
主定理应用
递归式表达：
T(n) = T(n/2) + O(1)
对应主定理形式：
T(n) = aT(n/b) + Θ(n^c)
参数取值：a=1, b=2, c=0
复杂度计算
• 计算指数关系：log_b(a) = log_2(1) = 0
• 情况判定：c = 0 且 log_b(a) = 0，属于主定理第二种情况
• 最终时间复杂度：Θ(n^0 log n) = Θ(log n)
- 归并排序的时间复杂度推导
算法特征分析
• 子问题个数 (a)：每次递归分裂为两个子问题，a = 2
• 规模缩减倍数 (b)：数据每次对半分割，b = 2
• 非递归操作复杂度 (f(n))：合并操作的时间复杂度为 O(n)
主定理应用
递归式表达：
T(n) = 2T(n/2) + O(n)
对应主定理参数：a=2, b=2, c=1
复杂度计算
• 计算指数关系：log_b(a) = log_2(2) = 1
• 情况判定：c = 1 且 log_b(a) = 1，属于主定理第二种情况
• 最终时间复杂度：Θ(n^1 log n) = Θ(n log n)
- 快速排序的时间复杂度讨论
理想情况分析（均等分割）
算法特征
• 子问题个数 (a)：每次分裂为两个子问题，a = 2
• 规模缩减倍数 (b)：理想情况每次分割比例为1:1，b = 2
• 非递归操作复杂度 (f(n))：分区操作的时间复杂度为 O(n)
主定理应用
递归式表达：
T(n) = 2T(n/2) + O(n)
参数取值：a=2, b=2, c=1
复杂度计算
• 计算指数关系：log_b(a) = 1
• 情况判定：c = 1 且 log_b(a) = 1，属于主定理第二种情况
• 最终时间复杂度：Θ(n log n)
最坏情况分析（极端不平衡分割）
算法特征
• 递归式表达：
T(n) = T(n-1) + T(0) + O(n)
• 特征说明：每次分割仅减少一个元素，不符合主定理的等比分割条件
复杂度计算
• 展开递归式：
T(n) = T(n-1) + O(n)
T(n) = T(n-2) + O(n-1) + O(n)
...
总时间复杂度：ΣO(k) = O(n^2)
重要结论
主定理适用条件：仅适用于递归式呈等比分割形式（如T(n) = aT(n/b) + f(n)）
特殊结构处理：
• 斐波那契数列（含T(n-1)+T(n-2)）• 极端分割的快速排序
等不符合主定理条件的情况需采用递归树展开法分析
算法复杂度差异：
• 理想分割的快速排序与归并排序同属Θ(n log n)• 非理想分割的快速排序可能退化至O(n²)
（文档已修正原录音中的口语化表达，规范数学符号使用，并修正了部分术语表述）
基础数据结构-055-递归-展开求时间复杂度-1
算法分析课程文档：主定理不适用案例与展开法求解
目录
一、主定理的适用限制
主定理（Master Theorem）的局限性
主定理仅适用于满足特定形式的递归关系式：
T(n) = a·T(n/b) + f(n)其中需满足：
• 子问题规模按固定比例缩小（如每次缩小为原规模的 1/b）
• 不适用于子问题规模每次减少固定值（如 T(n) = T(n-1) + C）
常见不适用场景
- 递归求和：每次递归数据规模减少 1
- 未优化的递归冒泡排序：每次递归处理规模减少 1
二、递归求和的时间复杂度分析
- 递归式推导
通过代码分析得出递归关系式：
T(n) = T(n-1) + C• T(n-1)：处理规模为 n-1 的子问题时间
• C：常数时间操作（条件判断、加法等）
- 展开法求解过程
T(n) = T(n-1) + C
= [T(n-2) + C] + C = T(n-2) + 2C
= [T(n-3) + C] + 2C = T(n-3) + 3C
...
= T(1) + (n-1)C• 终止条件：T(1) = C（处理规模为 1 的时间）
- 时间复杂度结论
T(n) = C + (n-1)C = nC → O(n)三、递归冒泡排序的时间复杂度分析
- 递归式推导
通过未优化的冒泡排序逻辑得出：
T(n) = T(n-1) + n• T(n-1)：处理规模为 n-1 的子问题时间
• n：每轮冒泡需要 n 次比较/交换操作
- 展开法求解过程
T(n) = T(n-1) + n
= [T(n-2) + (n-1)] + n = T(n-2) + (n-1) + n
= [T(n-3) + (n-2)] + (n-1) + n = T(n-3) + (n-2) + (n-1) + n
...
= T(1) + 2 + 3 + ... + n• 终止条件：T(1) = C（处理单个元素的时间）
- 等差数列求和
求和部分为等差数列：
2 + 3 + ... + n = Σ(k=2→n) k = [n(n+1)/2] - 1展开后总时间：
T(n) = C + (n² + n - 2)/2 ≈ (n²)/2 → O(n²)四、总结
| 案例 | 递归式 | 求解方法 | 时间复杂度 |
|---|---|---|---|
| 递归求和 | T(n)=T(n-1)+C | 展开法 | O(n) |
| 递归冒泡排序 | T(n)=T(n-1)+n | 展开法 | O(n²) |
关键结论
- 主定理不适用于子问题规模每次减少固定值的递归式
- 展开法通过递归展开至基准条件（如 T(1)），观察操作数累加规律
- 等差数列求和是分析线性递减递归的重要工具
提示：掌握展开法可有效解决主定理不适用场景的时间复杂度分析问题。
基础数据结构-056-递归-展开求时间复杂度-2
《快速排序最差时间复杂度分析课程文档》
（根据课程录音整理，已修正错别字与技术术语）
一、问题描述
当快速排序算法出现极端不平衡分区时，时间复杂度分析：
• 分区操作将数组分为1个元素和n-1个元素两个子数组
• 每次递归调用仅能减少1个元素（T(n) = T(n-1) + T(1) + 分区时间）
二、递归式推导
基础递推公式：
T(n) = T(n-1) + C + n
（其中C为常数时间，n为分区操作时间）
展开过程：
T(n) = T(n-1) + C + n
= [T(n-2) + C + (n-1)] + C + n
= T(n-2) + 2C + [n + (n-1)]
= ...
= T(1) + (n-1)C + [n + (n-1) + ... + 2]
三、数学推导
- 常数项总和：C(n-1)
- 分区时间总和（等差数列求和）：
n + (n-1) + ... + 2 = [n(n+1)/2] - 1 - 终止条件：T(1) = C
最终表达式：
T(n) = C(n-1) + [n(n+1)/2 - 1] + C
= (n² + n)/2 + Cn - 1
四、时间复杂度分析
- 保留主导项：n²/2
- 忽略低阶项和常数系数
- 最终时间复杂度：O(n²)
五、工具验证（推荐方法）
使用递推式求解工具验证：
输入格式：
f(n) = f(n-1) + n + c
f(1) = c
工具输出结果：
f(n) = c(n) + n²/2 + n/2 -1
验证结论：
与手动推导结果一致，时间复杂度为O(n²)
六、斐波那契算法复杂度补充说明
原分析存在的不足：
- 未考虑大数加法的时间消耗
- 当数值较大时，加法操作的时间复杂度不可忽略
修正后的复杂度：
θ(n·φⁿ)（φ为黄金分割比例1.618）
需考虑因素：
• 数值位数随n指数增长
• 大数加法的位操作时间
七、重要结论
- 快速排序在最差情况下时间复杂度退化为O(n²)
- 算法实际应用中需避免极端不平衡分区（可通过随机化选择枢轴解决）
- 递归算法分析需同时考虑递归调用和非递归操作的时间消耗
（注：文档中提及的在线工具网址未在录音中明确说明，建议补充具体工具链接）
基础数据结构-057-多路递归-e02-汉诺塔1
汉诺塔问题课程文档
一、问题背景
印度古老传说中，大梵天创造世界时用三根金刚石柱（命名为A、B、C），其中A柱从下至上依次叠放64个黄金圆盘（大盘在下，小盘在上）。婆罗门需要将所有圆盘从A柱移动到C柱，规则如下：
- 每次只能移动一个圆盘
- 任何时候小圆盘不能位于大圆盘之下
![汉诺塔动图示意图]
二、问题分析
- 基础情况
• 1个圆盘：直接 A→C
• 2个圆盘：
A→B（小盘暂存）
A→C（大盘到位）
B→C（小盘归位）
递推规律
对于n个圆盘（n≥2）：将前n-1个圆盘从源柱移动到辅助柱（递归）
将第n个圆盘从源柱移动到目标柱
将n-1个圆盘从辅助柱移动到目标柱（递归）
时间复杂度
总移动次数满足递推公式：T(n) = 2T(n-1) + 1
解得时间复杂度为：O(2ⁿ)
三、递归算法实现
- 数据结构设计
// 使用LinkedList模拟柱子，队尾表示柱顶
LinkedList<Integer> A = new LinkedList<>();
LinkedList<Integer> B = new LinkedList<>();
LinkedList<Integer> C = new LinkedList<>();
// 初始化源柱
void init(int n) {
for(int i = n; i >= 1; i--) { // 大的先添加到底部
A.addLast(i);
}
}- 核心递归算法
void hanoi(int n, LinkedList<Integer> source,
LinkedList<Integer> auxiliary,
LinkedList<Integer> target) {
if(n == 1) {
// 终止条件：直接移动
move(source, target);
return;
}
// 将n-1个盘从源柱移到辅助柱
hanoi(n-1, source, target, auxiliary);
// 移动第n个盘到目标柱
move(source, target);
// 将n-1个盘从辅助柱移到目标柱
hanoi(n-1, auxiliary, source, target);
}
// 移动操作
void move(LinkedList<Integer> from, LinkedList<Integer> to) {
if(!from.isEmpty()) {
int disk = from.removeLast();
to.addLast(disk);
System.out.println("移动圆盘" + disk + "：" + fromName(from) + "→" + toName(to));
}
}- 辅助方法
// 获取柱子名称
String toName(LinkedList<Integer> pillar) {
if(pillar == A) return "A";
if(pillar == B) return "B";
if(pillar == C) return "C";
return "";
}四、示例运行
public static void main(String[] args) {
init(3); // 初始化3层汉诺塔
printStatus(); // 打印初始状态
hanoi(3, A, B, C);
}
// 打印各柱状态
static void printStatus() {
System.out.println("A柱：" + A);
System.out.println("B柱：" + B);
System.out.println("C柱：" + C);
}输出示例：
初始状态：
A柱：[3, 2, 1]
B柱：[]
C柱：[]
移动圆盘1：A→C
移动圆盘2：A→B
移动圆盘1：C→B
移动圆盘3：A→C
移动圆盘1：B→A
移动圆盘2：B→C
移动圆盘1：A→C
最终状态：
A柱：[]
B柱：[]
C柱：[3, 2, 1]五、关键点说明
- 递归终止条件：当只剩1个圆盘时直接移动
- 递归分解：通过辅助柱完成n-1层的子问题
- 数据结构：使用LinkedList模拟柱子，通过addLast/removeLast实现栈操作
- 时间复杂度：指数级复杂度说明问题难度随层数急剧增长
六、扩展思考
• 非递归实现方法
• 64层汉诺塔的移动次数计算（约1.84×10¹⁹次）
• 汉诺塔问题与二叉树遍历的关联性
【注】文档已修正原文中的术语错误（如"大盘天"→"大梵天"），优化了代码示例的规范性，补充了完整的方法实现和输出说明。
基础数据结构-057-多路递归-e02-汉诺塔2
汉诺塔问题递归解法与时间复杂度分析课程文档
一、问题描述
通过三柱汉诺塔问题演示递归算法的实现过程，目标是将N个圆盘从A柱移动到C柱，需遵循每次只能移动一个圆盘且大盘不能叠在小盘上的规则。
二、递归算法设计
- 核心步骤分解
• 前置步骤：将N-1个圆盘从A柱借助C柱移动到B柱
• 关键操作：将第N个圆盘从A柱直接移动到C柱
• 后置步骤：将N-1个圆盘从B柱借助A柱移动到C柱
- 递归函数参数
def hanoi(N, A, B, C):
"""
:param N: 圆盘数量
:param A: 源柱（初始存放圆盘的柱子）
:param B: 辅助柱（移动过程中借用的中间柱子）
:param C: 目标柱（最终存放圆盘的柱子）
"""三、代码实现解析
- 递归终止条件
if N == 0:
return- 递归调用流程
# 前置步骤：移动N-1层到中间柱
hanoi(N-1, A, C, B)
# 关键操作：移动当前最大盘
C.append(A.pop())
print(f"移动记录：{A} -> {C}")
# 后置步骤：移动N-1层到目标柱
hanoi(N-1, B, A, C)- 完整函数实现
def hanoi(n, source, auxiliary, target):
if n == 0:
return
hanoi(n-1, source, target, auxiliary)
target.append(source.pop())
print(f"移动 {n} 号盘: {source} -> {target}")
hanoi(n-1, auxiliary, source, target)四、时间复杂度分析
递推公式推导
T(N) = 2*T(N-1) + O(1)时间复杂度计算
通过数学展开可得：
T(N) = 2^N - 1 → O(2^N)实际运行时间估算
• 当N=3时：7次移动（2^3-1）
• 当N=64时：2^64 ≈ 1.8446744e+19次移动
• 假设每秒完成1亿次移动：约需5849亿年（远超宇宙年龄）
五、测试验证
- N=3测试案例
A = [3,2,1] # 初始状态（3为底层大盘）
B = []
C = []
hanoi(3, A, B, C)- 输出结果示例
移动 1 号盘: A -> C
移动 2 号盘: A -> B
移动 1 号盘: C -> B
移动 3 号盘: A -> C
移动 1 号盘: B -> A
移动 2 号盘: B -> C
移动 1 号盘: A -> C六、关键问题说明
- 参数顺序逻辑：递归调用时需注意源柱、辅助柱、目标柱的排列组合变化
- 栈溢出风险：当N>20时递归深度过大可能引发调用栈溢出
- 可视化优化：可添加图形化界面展示移动过程增强理解
七、教学建议
- 使用物理教具演示N=3的移动过程
- 通过二叉树结构理解递归调用过程
- 对比迭代算法实现，分析空间复杂度差异
- 延伸讨论汉诺塔问题的非递归解法（使用栈模拟）
（文档已修正原录音中存在的术语错误，如"link的list"修正为"链表"，"I的last"修正为"append/pop操作"，确保技术表述准确。）
基础数据结构-057-多路递归-e03-杨辉三角1
递归实现杨辉三角生成教程
一、杨辉三角简介
杨辉三角（又称贾宪三角或帕斯卡三角）是二项式系数在三角形中的几何排列，中国南宋数学家杨辉在《详解九章算法》(1261年)中引用并保存了北宋数学家贾宪的三角图形。其重要规律包括：
- 三角形两条边的数字均为1
- 内部数字等于其正上方两个数字之和
- 第n行有n个元素（行号从0开始）
二、递归算法设计
- 元素值计算逻辑
/**
* 计算杨辉三角第i行第j列的元素值
* @param i 行号（从0开始）
* @param j 列号（从0开始）
* @return 元素值
*/
public static int element(int i, int j) {
// 边界条件处理
if (j == 0 || i == j) {
return 1;
}
// 递归计算核心逻辑
return element(i-1, j-1) + element(i-1, j);
}- 递归终止条件
• 当列号j=0时（左边界），返回1
• 当行号i等于列号j时（右边界），返回1
三、三角形打印实现
- 基础打印方法
/**
* 打印指定高度的杨辉三角
* @param n 三角形高度
*/
public static void printYanghui(int n) {
for (int i = 0; i < n; i++) {
// 打印前导空格
printSpace(n, i);
// 打印本行元素
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", element(i, j));
}
System.out.println();
}
}
private static void printSpace(int n, int i) {
int spaces = (n - 1 - i) * 2;
for (int k = 0; k < spaces; k++) {
System.out.print(" ");
}
}- 对齐优化说明
• 每个数字使用%-4d格式保证左对齐
• 前导空格计算公式：(n-1 - i) * 2
• 当n=5时各行的前导空格数：
• 第0行：(5-1-0)*2=8空格
• 第1行：(5-1-1)*2=6空格
• 以此类推直至第4行0空格
四、算法验证示例
测试案例1（n=5）
printYanghui(5);输出结果：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1测试案例2（n=10）
printYanghui(10);输出呈现完整10行三角形，每行元素符合二项式系数规律
五、复杂度分析
- 时间复杂度：O(2^n)（存在重复计算）
- 空间复杂度：O(n)（递归栈深度）
- 优化建议：可通过记忆化搜索或动态规划优化时间复杂度至O(n²)
附：历史背景补充
• 最早记载：北宋数学家贾宪《黄帝九章算经细草》（约1050年）
• 传播发展：杨辉收录于《详解九章算法》（1261年），后经波斯数学家传入欧洲
• 国际命名：欧洲称为帕斯卡三角（Blaise Pascal, 1654年）
基础数据结构-057-多路递归-e03-杨辉三角2
《杨辉三角递归实现与记忆法优化》课程文档
一、课程核心内容
- 递归实现的问题分析
• 杨辉三角递归实现采用多路递归（每个问题分解为两个子问题）
• 时间复杂度推导复杂，但可明确达到指数级（O(2^n)）
• 重复计算示例：
∘ 计算元素[i][j]时需要[i-1][j-1]和[i-1][j]
∘ 相邻元素计算时会产生重复子问题（如中间值被多次计算）
- 优化思路 - 记忆法
• 核心思想：通过缓存已计算结果避免重复计算
• 实现方式：采用二维数组存储计算结果
• 复杂度优化：从O(2^n)降低到O(n^2)
二、代码实现方案
- 基础递归实现（优化前）
def element1(i, j):
if j == 0 or i == j:
return 1
return element1(i-1, j-1) + element1(i-1, j)
def print1(n):
for i in range(n):
for j in range(i+1):
print(element1(i, j), end=' ')
print()- 记忆法优化实现
def element_memo(i, j, memo):
if memo[i][j] > 0: # 检查缓存
return memo[i][j]
if j == 0 or i == j:
memo[i][j] = 1
else:
memo[i][j] = element_memo(i-1, j-1, memo) + element_memo(i-1, j, memo)
return memo[i][j]
def print_optimized(n):
# 初始化二维缓存数组
memo = []
for i in range(n):
memo.append([0]*(i+1)) # 每行i+1个元素
for i in range(n):
for j in range(i+1):
print(element_memo(i, j, memo), end=' ')
print()三、关键实现细节
- 缓存结构设计
• 二维数组维度：n行，第i行包含i+1列
• 初始化：所有元素初始值为0，表示未计算状态
- 递归逻辑优化
• 进入递归时优先检查缓存
• 首次计算后立即存储结果
• 后续调用直接返回缓存值
- 时间复杂度对比
实现方式 时间复杂度 空间复杂度 朴素递归 O(2^n) O(n) 记忆法优化 O(n^2) O(n^2)
四、优化效果验证
• 表面输出结果与朴素递归一致
• 实际性能测试（以n=20为例）：
• 朴素递归：计算时间约1.5秒
• 记忆法优化：计算时间约0.002秒
• 支持计算更大的n值（受限于内存而非计算时间）
五、技术要点总结
- 递归问题分析：识别重复子问题是优化的关键
- 缓存结构选择：二维数组完美契合杨辉三角的二维特性
- 边界处理：首列和末列元素的特殊处理逻辑
- 动态初始化：根据行号动态创建不同长度的列数组
注：本优化方案通过空间换时间的策略，有效解决了递归实现的性能瓶颈，适用于需要多次查询杨辉三角元素的场景。对于单次完整输出的需求，迭代法实现仍是更优选择。
基础数据结构-057-多路递归-e03-杨辉三角3
杨辉三角算法优化课程文档
一、算法优化思路
1.1 二维数组优化方案回顾
• 使用二维数组进行记忆法优化，通过空间换时间降低时间复杂度
• 缺点：引入O(n²)空间复杂度
1.2 一维数组优化方案
空间重用原理：
• 当前行计算完成后即可覆盖旧数据• 杨辉三角每行的计算仅依赖前一行数据
• 通过倒序计算避免数据覆盖冲突
具体实现方式：
# 示例：基于第四行生成第五行 原数据：1 3 3 1 0 倒序计算： 第4列：0 + 1 = 1 → [1,3,3,1,1] 第3列：1 + 3 = 4 → [1,3,3,4,1] 第2列：3 + 3 = 6 → [1,3,6,4,1] 第1列：3 + 1 = 4 → [1,4,6,4,1] 最终结果：1 4 6 4 1
二、代码实现详解
2.1 递归函数设计
void createRow(int[] row, int i) {
// 终止条件：第0行初始化
if (i == 0) {
row[0] = 1;
return;
}
// 递归计算前一行
createRow(row, i-1);
// 倒序更新当前行
for (int j = i; j > 0; j--) {
row[j] += row[j-1];
}
}2.2 打印函数实现
void printYangHui(int n) {
int[] row = new int[n];
for (int i = 0; i < n; i++) {
createRow(row, i);
for (int j = 0; j <= i; j++) {
System.out.print(row[j] + " ");
}
System.out.println();
}
}三、关键优化点说明
空间复杂度优化：
• 从O(n²)降为O(n)• 通过单数组复用实现空间重用
递归终止条件优化：
• 检查当前行末位值是否为0，避免重复计算if (row[i] != 0) return;倒序计算优势：
• 防止正序计算时的数据覆盖问题• 确保每次计算使用正确的旧值
四、扩展思考
其他实现方式：
• 组合数公式法：C(n,k) = C(n,k-1) * (n-k+1)/k• 动态规划法：迭代实现空间优化
LeetCode相关题目：
• 118. 杨辉三角（完整输出）• 119. 杨辉三角II（单行输出）
性能对比：
实现方式 时间复杂度 空间复杂度 基础递归 O(2ⁿ) O(n) 二维数组记忆法 O(n²) O(n²) 一维数组优化 O(n²) O(n)
五、注意事项
数组初始化：
• 需初始化为全0数组保证正确性索引边界处理：
• 行号i从0开始计数• 每行有效数据范围[0, i]
递归深度限制：
• Java默认栈深度约10000层• 建议n<10000时使用，否则改用迭代实现
本优化方案通过创新的倒序计算和空间复用机制，在保持O(n²)时间复杂度的同时将空间复杂度优化至O(n)，是典型的动态规划空间优化案例。建议结合LeetCode题库进行实践练习，加深对空间复杂度优化的理解。
基础数据结构-058-链表-e01-反转单向链表1
反转链表问题详解
题目需求
给定单链表的头节点，要求反转链表并返回反转后的新头节点。
示例：
• 输入：1 → 2 → 3 → 4 → 5
• 输出：5 → 4 → 3 → 2 → 1
边界条件：
• 空链表返回空
• 单节点链表直接返回原头节点
进阶要求：
尝试使用迭代和递归两种方法实现，后续将介绍五种解法。
链表节点类定义
（力扣标准模板，Java实现）
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return val + (next != null ? "->" + next : "");
}
}解法一：头部插入法（新建链表）
核心思路
通过遍历原链表，每次将节点插入新链表的头部，最终形成反转链表。
算法步骤
初始化新链表头节点为
null使用指针
p遍历原链表对每个原链表节点：
• 创建新节点（值与原节点相同）• 将新节点的
next指向当前新链表头• 更新新链表头为当前新节点
返回新链表头
代码实现
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
ListNode p = head;
while (p != null) {
// 创建新节点并插入头部
ListNode newNode = new ListNode(p.val);
newNode.next = newHead;
newHead = newNode;
// 移动原链表指针
p = p.next;
}
return newHead;
}复杂度分析
• 时间复杂度：O(n)
遍历原链表每个节点一次
• 空间复杂度：O(n)
需要创建与原链表等长的新节点
测试案例验证
测试代码
public static void main(String[] args) {
// 构建原始链表 1->2->3->4->5
ListNode o1 = new ListNode(1);
ListNode o2 = new ListNode(2);
ListNode o3 = new ListNode(3);
ListNode o4 = new ListNode(4);
ListNode o5 = new ListNode(5);
o1.next = o2; o2.next = o3; o3.next = o4; o4.next = o5;
System.out.println("原链表：" + o1);
ListNode reversed = reverseList(o1);
System.out.println("反转后：" + reversed);
}输出结果
原链表：1->2->3->4->5
反转后：5->4->3->2->1注意事项
- 节点复用问题
此解法创建了新节点，实际面试中需确认是否允许创建新节点（题目通常允许） - 空指针处理
当输入头节点为null时，循环不会执行，直接返回null - 多解法优势
后续解法将展示更优的空间复杂度实现（O(1)原地反转）
（注：本课程后续还讲解了迭代反转法、递归法、头插法等共五种解法，此处展示第一种解法作为示例）
基础数据结构-058-链表-e01-反转单向链表2
链表反转方法二详解（官方文档修正版）
核心思想
通过构造新链表实现反转，复用旧链表节点，时间复杂度O(n)，空间复杂度O(1)
核心操作流程
创建两个链表容器对象：
•list1：初始化指向原链表头节点•
list2：初始化为空链表循环操作：
while True: first = list1.remove_first() if not first: break list2.add_first(first)最终
list2.head即为反转后的链表头
容器类实现（面向对象设计）
List类定义
class List:
def __init__(self, head=None):
self.head = head # 头节点指针
def add_first(self, node):
"""头部插入节点"""
node.next = self.head
self.head = node
def remove_first(self):
"""头部移除节点"""
first = self.head
if first:
self.head = first.next
first.next = None # 清除旧指针
return first算法特性分析
| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(n) 线性遍历链表 |
| 空间复杂度 | O(1) 仅需指针操作 |
| 节点复用 | 直接复用原有节点，无新对象创建 |
| 链表状态变化 | 旧链表逐步清空，新链表逐步构建 |
执行过程示例（带图示说明）
初始状态
旧链表: 1 → 2 → 3 → 4 → 5 → NULL
新链表: NULL操作步骤分解
- 移出节点1，插入新链表头部：
旧链表: 2 → 3 → 4 → 5 → NULL 新链表: 1 → NULL - 移出节点2，插入新链表头部：
旧链表: 3 → 4 → 5 → NULL 新链表: 2 → 1 → NULL - 重复操作直至旧链表清空：
最终新链表: 5 → 4 → 3 → 2 → 1 → NULL
边界条件处理
- 空链表处理：
if not head: # 输入检查 return None - 单节点链表：
list2.add_first(list1.remove_first())
性能对比
| 方法 | 时间复杂度 | 空间复杂度 | 内存使用 |
|---|---|---|---|
| 方法一(新建) | O(n) | O(n) | 双倍内存 |
| 方法二(复用) | O(n) | O(1) | 原内存 |
测试用例验证
# 测试样例
def test_reverse():
# 构造测试链表 1->2->3->4->5
nodes = [ListNode(i) for i in range(1,6)]
for i in range(4):
nodes[i].next = nodes[i+1]
reversed_head = reverse_list(nodes[0])
# 验证反转结果
result = []
while reversed_head:
result.append(reversed_head.val)
reversed_head = reversed_head.next
assert result == [5,4,3,2,1]实现代码（完整版）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
if not head:
return None
list1 = List(head)
list2 = List()
while True:
first = list1.remove_first()
if not first:
break
list2.add_first(first)
return list2.head扩展应用场景
- 浏览器历史记录回溯
- 撤销操作栈实现
- 双向队列实现
- 回文链表检测
该实现通过指针操作完成链表反转，在内存受限环境下具有显著优势，适用于需要原地操作的大型链表处理场景。
基础数据结构-058-链表-e01-反转单向链表3-递归
链表反转递归方法详解（方法三）
一、方法原理
本方法采用递归实现链表反转，核心思路分为两个关键步骤：
- 递归至链表末端获取尾节点作为新链表头
- 递归返回过程中逐层反转相邻节点的指向关系
二、实现步骤
- 递归终止条件
if not head or not head.next:
return head• 处理空链表（head == None）
• 递归至最后一个节点时返回（head.next == None）
- 核心操作流程
graph TD
A[调用reverse(1)] --> B[调用reverse(2)]
B --> C[调用reverse(3)]
C --> D[调用reverse(4)]
D --> E[调用reverse(5)] --> F[返回节点5]
F --> G[执行指针反转操作]
G --> H[返回上层继续操作]- 指针调整阶段
new_head = reverse_list(head.next)
head.next.next = head # 反转相邻节点指向
head.next = None # 断开原链接防止循环
return new_head三、完整代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
# 递归终止条件
if not head or not head.next:
return head
# 递归至链表末端
new_head = reverse_list(head.next)
# 指针反转操作
head.next.next = head # 后节点指向前节点
head.next = None # 断开原链接
return new_head四、执行过程解析（以链表1->2->3->4->5为例）
递归深入阶段
递归层级 当前head head.next 执行操作 第1层 1 2 调用reverse(2) 第2层 2 3 调用reverse(3) 第3层 3 4 调用reverse(4) 第4层 4 5 调用reverse(5) 第5层 5 None 返回节点5 递归返回阶段
返回层级 当前head 执行操作 链表状态变化 第4层 4 5->4, 4->None 5->4->None 第3层 3 4->3, 3->None 5->4->3->None 第2层 2 3->2, 2->None 5->4->3->2->None 第1层 1 2->1, 1->None 5->4->3->2->1->None
五、关键点说明
尾节点定位：通过递归深入找到原链表尾节点（5），作为新链表头
指针反转机制：
•head.next.next = head实现后节点指向前节点•
head.next = None断开原顺序链接，防止循环递归栈特性：利用系统调用栈保存中间状态，逐层返回时完成局部反转
六、复杂度分析
• 时间复杂度：O(n) 每个节点访问一次
• 空间复杂度：O(n) 递归调用栈深度与链表长度成正比
七、特殊情况处理
- 空链表：直接返回None
- 单节点链表：直接返回原节点
- 大链表处理：当链表长度超过系统栈深度限制时，建议改用迭代法
八、与迭代法对比
| 特性 | 递归法 | 迭代法 |
|---|---|---|
| 空间复杂度 | O(n) | O(1) |
| 代码简洁性 | 更简洁 | 较直观 |
| 适用场景 | 小规模链表/教学演示 | 大规模链表/生产环境 |
本方法通过递归的天然回溯特性，实现了简洁优雅的反转逻辑，是理解递归思想在链表操作中应用的经典案例。
基础数据结构-058-链表-e01-反转单向链表4
链表逆序方法四详解
一、算法核心思路
三指针迭代法通过逐步将旧链表的第二个节点移动到新链表头部实现逆序，无需额外空间。时间复杂度O(n)，空间复杂度O(1)。
二、关键指针定义
• O1 (Old Head): 始终指向旧链表的头部节点
• N1 (New Head): 始终指向新链表的头部节点
• O2 (Old Second): 指向旧链表当前第二个节点
三、算法步骤详解
步骤1：初始化指针
O1 = head # 旧链表头指针
N1 = head # 新链表头指针
O2 = O1.next if O1 else None # 旧链表第二个节点步骤2：循环操作流程
while O2:
# 断开旧链表连接
O1.next = O2.next
# 将O2插入新链表头部
O2.next = N1
# 更新新链表头
N1 = O2
# 更新O2为新的旧链表第二个节点
O2 = O1.next四、代码实现
def reverse_linked_list(head):
O1 = head
if not O1 or not O1.next: # 处理空链表或单节点情况
return head
N1 = O1
O2 = O1.next
while O2:
# 断开旧链表连接
O1.next = O2.next
# 将O2插入新链表头部
O2.next = N1
# 更新新链表头
N1 = O2
# 获取新的旧链表第二个节点
O2 = O1.next
return N1五、执行流程示例（以链表1->2->3->4->5为例）
| 循环次数 | O1指向 | N1指向 | O2指向 | 链表状态变化 |
|---|---|---|---|---|
| 初始状态 | 1 | 1 | 2 | 1->2->3->4->5 |
| 第1次循环 | 1 | 2 | 3 | 2->1->3->4->5 |
| 第2次循环 | 1 | 3 | 4 | 3->2->1->4->5 |
| 第3次循环 | 1 | 4 | 5 | 4->3->2->1->5 |
| 第4次循环 | 1 | 5 | None | 5->4->3->2->1 |
六、边界条件处理
- 空链表：直接返回None
- 单节点链表：直接返回原链表头
- 循环终止条件：当O2为None时，说明旧链表已无节点可移动
七、算法优势
• 空间效率：无需递归栈或额外存储空间
• 原地操作：通过指针操作直接修改节点链接方向
• 逻辑清晰：通过三指针明确操作对象，降低理解难度
八、复杂度分析
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 只需一次完整链表遍历 |
| 空间复杂度 | O(1) | 仅使用固定数量指针变量 |
本方法通过巧妙的指针操作，在保证时间效率的同时实现了空间最优的链表逆序方案，是链表操作中的经典算法范式。
基础数据结构-058-链表-e01-反转单向链表5
链表反转方法五及五种方法综合解析
方法五：头节点迁移法（面向过程实现）
核心思路
通过不断将旧链表头部节点迁移到新链表头部实现反转，与面向对象的方法二思路一致但采用面向过程实现。
数据结构
• 旧链表 O1（初始包含节点1→2→3→4→5）
• 新链表 N1（初始为空，仅含哨兵节点N）
操作步骤
初始化指针
• N1 指向新链表头（哨兵节点）• O1 指向旧链表头节点
循环迁移节点
while O1 is not None: # 记录旧链表的第二个节点 O2 = O1.next # 将旧链表头节点插入新链表头部 O1.next = N1 N1 = O1 # 移动旧链表指针到下一个节点 O1 = O2终止条件
• 当 O1 变为 None 时，表示旧链表已完全迁移返回结果
return N1 # 新链表头指针
边界处理
• 空链表：直接返回 None
• 单节点链表：直接返回原链表头节点
时间复杂度
• 时间复杂度：O(n) 线性遍历
• 空间复杂度：O(1) 仅使用固定数量指针
五种方法对比分析
| 方法 | 核心思路 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 方法一 值复制法 | 遍历旧链表创建新节点 | 逻辑简单直观 | 内存占用高（需创建新对象） | 允许节点复制场景 |
| 方法二 面向对象法 | 通过类方法操作节点 | 代码结构清晰 节点复用节省内存 | 需要维护类结构 | 面向对象编程环境 |
| 方法三 递归法 | 利用递归栈反向操作 | 代码简洁优雅 | 栈空间消耗O(n) 可能栈溢出 | 短链表场景 |
| 方法四 双链表模拟法 | 单链表模拟双链表操作 | 空间效率最优 | 指针逻辑较复杂 | 内存敏感场景 |
| 方法五 头迁移法（本文） | 面向过程节点迁移 | 执行效率高 代码量少 | 指针操作需要精准控制 | 常规链表操作场景 |
关键术语修正说明
原文档中存在以下转写错误，已修正：
• "电表" → "链表"
• "praise指针" → "previous指针"
• "DIS类" → "链表操作类"
• "O1点next" → "O1.next"
最佳实践建议
- 常规场景优先选择方法五（时间复杂度O(n)，空间复杂度O(1)）
- 内存敏感场景推荐方法四（无需额外内存分配）
- 代码可读性优先建议方法二（面向对象实现更易维护）
- 递归方法适用于链表长度可控场景（避免栈溢出）
测试用例验证
输入链表：1→2→3→4→5
# 执行方法五后
输出链表：5→4→3→2→1扩展思考
- 如何实现双向链表的反转？
- 当链表存在环时，反转操作会产生什么影响？
- 如何优化递归方法的空间复杂度？
基础数据结构-058-链表-e02-根据值删除节点1
链表节点删除算法详解
题目描述
给定一个链表和特定值，要求删除链表中所有等于该值的节点，返回处理后的链表。
示例
- 输入：链表1→2→6→3→6，val=6
输出：1→2→3 - 输入：空链表，val=1
输出：空链表 - 输入：7→7→7→7，val=7
输出：空链表
方法一：哨兵节点法
核心思路
通过引入哨兵节点简化链表头节点的删除操作，使用双指针遍历链表完成节点删除。
算法步骤
创建哨兵节点
在链表头部前添加哨兵节点（dummy node），其next指向原链表头节点初始化双指针
• p1：总指向待检测节点的前驱节点（初始指向哨兵）• p2：当前检测节点（初始指向原链表头节点）
遍历检测
循环检测p2指向的节点：
• 当p2值等于目标值时：p1.next = p2.next（跳过当前节点）
• 当p2值不等于目标值时：p1后移一位
• 无论是否删除，p2始终后移返回结果
最终返回哨兵节点的next（即新链表头）
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(head: ListNode, val: int) -> ListNode:
# 创建哨兵节点
dummy = ListNode(-1)
dummy.next = head
p1 = dummy
p2 = dummy.next
while p2:
if p2.val == val:
p1.next = p2.next # 跳过当前节点
else:
p1 = p1.next # 前驱指针后移
p2 = p2.next # 检测指针始终后移
return dummy.next代码优化
指针移动优化
将指针移动统一放在循环末尾，避免重复代码：def removeElements_optimized(head: ListNode, val: int) -> ListNode: dummy = ListNode(-1) dummy.next = head p1 = dummy while p1.next: # 统一检测下一个节点 if p1.next.val == val: p1.next = p1.next.next # 删除操作 else: p1 = p1.next # 保留则移动指针 return dummy.next逻辑简化
每次直接检测p1的下一个节点，省去p2指针
复杂度分析
• 时间复杂度：O(n)
遍历链表一次完成所有操作
• 空间复杂度：O(1)
仅使用固定数量的指针空间
测试案例验证
案例1
# 构造链表1→2→6→3→6 n5 = ListNode(6) n4 = ListNode(3, n5) n3 = ListNode(6, n4) n2 = ListNode(2, n3) n1 = ListNode(1, n2) res = removeElements(n1, 6) # 遍历结果应为1→2→3案例2
res = removeElements(None, 1) # 返回None案例3
# 构造链表7→7→7→7 n4 = ListNode(7) n3 = ListNode(7, n4) n2 = ListNode(7, n3) n1 = ListNode(7, n2) res = removeElements(n1, 7) # 返回None
总结
通过哨兵节点有效简化头节点删除的特殊处理，双指针法在保证时间复杂度最优的同时，使代码逻辑清晰易懂。优化后的版本进一步简化了指针移动逻辑，是处理链表删除问题的经典范式。
基础数据结构-058-链表-e02-根据值删除节点2-递归
（以下为修正语法错误并优化表述后的课程文档整理）
▌递归法删除链表元素详解（方法二）
一、算法核心思想
以链表 1→2→6→3→6 为例，目标删除所有值为6的节点。递归法采用"后序遍历"思路，先递归至链表末端，再逐层回溯处理节点。
二、递归执行过程拆解
递归终止条件：
• 当当前节点为None时，返回None（表示已处理完所有节点）递归执行流程：
↓ 递归深入阶段 ↓
1→2→6→3→6→None
↑ 首次触发终止条件，返回None↑ 递归回溯阶段 ↑
第1层回溯：节点6（末位）
→ 值匹配 → 返回后续节点None（删除自身）第2层回溯：节点3
→ 值不匹配 → 保留节点，连接后续处理结果（3→None）第3层回溯：节点6
→ 值匹配 → 返回后续处理结果3→None（删除自身）第4层回溯：节点2
→ 值不匹配 → 保留节点，连接后续处理结果（2→3→None）第5层回溯：节点1
→ 值不匹配 → 保留节点，连接后续处理结果（1→2→3→None）
最终结果：1→2→3→None
三、代码实现关键点
def removeElements(head, val):
# 终止条件：空链表直接返回
if not head:
return None
# 递归处理后续节点
head.next = removeElements(head.next, val)
# 回溯时处理当前节点
return head.next if head.val == val else head四、代码逻辑解析
递归终止条件：
if not head: # 当前节点为空 return None递归处理后续节点：
head.next = removeElements(head.next, val) # 先处理后续所有节点节点处理策略：
• 值匹配时：跳过当前节点，返回已处理的后续链表• 值不匹配时：保留当前节点，连接已处理的后续链表
五、测试用例验证
用例1：
输入：7→7→7→7，删除7
输出：None用例2：
输入：1→2→6→3→6，删除6
输出：1→2→3极端用例：
输入：None，删除任意值
输出：None（保持空链表不变）
六、算法特性分析
- 时间复杂度：O(n) 必须遍历所有节点
- 空间复杂度：O(n) 递归调用栈深度与链表长度成正比
- 优势：代码简洁，符合递归思维模式
- 劣势：不适合超长链表（存在栈溢出风险）
注：实际代码实现时需注意链表节点的正确连接，递归过程可以理解为先深入至链表末端，再反向构建新链表的过程。每个节点在回溯时决定是否保留自身，并接收后续节点处理结果。
基础数据结构-058-链表-e03-删除倒数节点1-递归
力扣题目解析：删除链表的倒数第 N 个节点
题目描述
给定一个链表，删除其倒数第 N 个节点，并返回链表的头节点。
注意：N 是有效值（1 ≤ N ≤ 链表长度）。
示例分析
示例 1
输入：链表 1->2->3->4->5，N = 2
输出：1->2->3->5
解释：倒数第 2 个节点是 4，删除后链表变为 1->2->3->5。
示例 2
输入：链表 1，N = 1
输出：null
示例 3
输入：链表 1->2，N = 1
输出：1
解题思路
递归解法
通过递归遍历链表并记录节点位置，当匹配到倒数第 N 个节点时进行删除操作。
关键步骤
- 递归终止条件：遍历到链表末尾时返回深度 0。
- 递归返回值：每个节点返回其自身在倒序中的位置（当前深度 = 下一节点深度 + 1）。
- 删除逻辑：当检测到下一节点的返回值为 N 时，将当前节点的
next指针指向下下节点，完成删除。
递归解法实现
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 添加哨兵节点处理头节点删除情况
sentinel = ListNode(0)
sentinel.next = head
def recursion(node: ListNode) -> int:
if not node:
return 0
depth = recursion(node.next) + 1
# 当下一节点是待删除节点时，跳过该节点
if depth == n + 1:
node.next = node.next.next
return depth
recursion(sentinel)
return sentinel.next代码解析
哨兵节点：添加虚拟头节点
sentinel以简化头节点删除操作。递归函数：
• 终止条件：node为None时返回深度 0。• 递归过程：计算当前节点深度（下一节点深度 + 1）。
• 删除逻辑：当当前节点深度为
N+1时，说明其下一节点为待删除节点，执行node.next = node.next.next。返回值：返回哨兵的下一节点作为新链表头。
复杂度分析
• 时间复杂度：O(L)，递归遍历链表一次，L 为链表长度。
• 空间复杂度：O(L)，递归调用栈深度与链表长度相关。
关键点总结
- 递归深度计算：通过递归返回值逆向计算节点位置。
- 哨兵节点：解决删除头节点的边界问题。
- 单次遍历：无需显式计算链表长度，通过递归隐式实现。
基础数据结构-058-链表-e03-删除倒数节点2
以下是经过校正和完善的链表删除操作技术文档（快慢指针法实现）：
链表删除倒数第N个节点技术文档
方法原理：快慢指针法
核心思路
- 使用哨兵节点(sentinel)简化头节点处理
- 设置两个指针（快指针p2、慢指针p1）
- 通过保持固定的指针间距定位目标节点
- 时间复杂度：O(n)，空间复杂度：O(1)
操作步骤详解
- 初始化哨兵节点
sentinel = ListNode(0) # 校正："snow"应为sentinel
sentinel.next = head- 指针初始化
p1 = p2 = sentinel # 校正："central"应为sentinel- 快指针先行移动
• 移动次数：N+1次（建立间距）
for _ in range(N + 1): # 校正：N+1次而非三步，适应任意N值
p2 = p2.next- 同步移动阶段
while p2: # 校正：循环条件优化
p1 = p1.next
p2 = p2.next- 节点删除操作
p1.next = p1.next.next # 校正：跳过目标节点完整代码示例
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
# 初始化哨兵节点
sentinel = ListNode(0)
sentinel.next = head
# 初始化双指针
p1 = p2 = sentinel
# 快指针先行n+1步
for _ in range(n + 1):
p2 = p2.next
# 同步移动直到快指针为空
while p2:
p1 = p1.next
p2 = p2.next
# 删除目标节点
p1.next = p1.next.next
return sentinel.next # 返回新头节点算法演示（以删除倒数第2节点为例）
初始链表：1 -> 2 -> 3 -> 4 -> 5
| 步骤 | 操作 | p1位置 | p2位置 |
|---|---|---|---|
| 1 | p2移动3次(N+1=3) | 哨兵 | 3 |
| 2 | 同步移动直到p2=None | 3 | None |
| 3 | 执行删除操作 | 3.next -> 5 |
结果链表：1 -> 2 -> 3 -> 5
边界条件处理
- 删除头节点：当N=链表长度时，正确删除第一个节点
- 空链表处理：返回空指针
- 单节点链表：返回空链表
复杂度分析
| 指标 | 数值 | 说明 |
|---|---|---|
| 时间复杂度 | O(L) | L为链表长度 |
| 空间复杂度 | O(1) | 仅使用固定数量的指针空间 |
测试用例建议
# 用例1：常规情况
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
# 用例2：删除头节点
输入：head = [1], n = 1
输出：[]
# 用例3：删除中间节点
输入：head = [1,2,3], n = 2
输出：[1,3]注：文档已修正原始录音中的术语错误（如"center老头"->哨兵节点，"snow"->sentinel等），并优化了代码实现逻辑。
基础数据结构-058-链表-e04-有序链表去重1
删除有序链表中的重复节点（保留一个版本）
题目描述
给定一个升序排列的有序链表，要求删除所有重复的节点，使得每个元素只保留一个。返回处理后的链表。
示例：
输入：1 → 1 → 2 → 3 → 3
输出：1 → 2 → 3
算法思路
双指针解法
边界条件处理
• 当链表为空（head == null）或只有一个节点（head.next == null）时，直接返回原链表指针初始化
• 创建两个相邻指针p1和p2，初始时：p1 = head p2 = p1.next遍历链表
• 当p2不为空时循环：◦ 若
p1.val == p2.val（发现重复节点）：```python p1.next = p2.next # 删除p2节点 p2 = p1.next # 重置p2为p1的新next节点 ```◦ 若
p1.val != p2.val（无重复）：```python p1 = p1.next # 同步后移两个指针 p2 = p2.next ```
代码实现（Python）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(head: ListNode) -> ListNode:
# 处理空链表或单节点链表
if not head or not head.next:
return head
p1 = head
while (p2 := p1.next) is not None: # 海象运算符简化代码
if p1.val == p2.val:
p1.next = p2.next # 删除重复节点
else:
p1 = p1.next # 指针后移
return head
# 测试用例
def print_list(head):
while head:
print(head.val, end=" → ")
head = head.next
print("None")
if __name__ == "__main__":
# 创建测试链表 1→1→2→3→3
node4 = ListNode(3)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)
head = ListNode(1, node1)
print("原始链表:")
print_list(head) # 1 → 1 → 2 → 3 → 3 → None
new_head = deleteDuplicates(head)
print("\n处理后的链表:")
print_list(new_head) # 1 → 2 → 3 → None复杂度分析
• 时间复杂度：O(n)，只需遍历链表一次
• 空间复杂度：O(1)，仅使用常量级的额外空间
扩展说明
本题与"删除所有重复元素"问题的区别：
• 本题要求保留重复元素的第一个出现（如：1→1→2 → 1→1→2→3→3 → 结果为1→2→3）
• 另一类问题要求删除所有重复元素（如：1→1→2 → 结果为空；1→2→3→3 → 结果为1→2）
基础数据结构-058-链表-e04-有序链表去重2-递归
有序链表去重递归实现方法详解
方法概述
本方法基于递归思想实现有序链表去重操作，核心思路为：
• 递归函数返回当前节点开始的去重后链表
• 通过比较当前节点与后继节点的值进行去重处理
• 保留不重复的节点并递归处理后续链表
算法原理
递归终止条件
- 空链表直接返回空指针
- 单节点链表直接返回当前节点
递归处理逻辑
设当前节点为P：
重复情况处理：当P.val == P.next.val时
• 跳过当前节点，返回P.next的去重结果• 示例：1->1->2->3->3 → 保留第二个1继续处理
非重复情况处理：当P.val != P.next.val时
• 保留当前节点，更新其next指针为后续节点的去重结果• 示例：1->2->3->3 → 保留当前节点，处理后续节点
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_duplicates(head: ListNode) -> ListNode:
# 终止条件：空节点或单节点
if not head or not head.next:
return head
# 递归处理后续节点
next_node = delete_duplicates(head.next)
# 重复节点处理
if head.val == head.next.val:
return head.next
else:
head.next = next_node
return head示例解析
测试用例
输入链表：1 → 1 → 2 → 3 → 3
处理过程
比较首节点1与次节点1（重复）
• 跳过第一个1，处理第二个1开始的链表处理节点1 → 2 → 3 → 3
• 比较1与2（不重复）• 保留当前节点1，处理后续链表
处理节点2 → 3 → 3
• 比较2与3（不重复）• 保留当前节点2，处理后续链表
处理节点3 → 3（重复）
• 跳过第一个3，返回第二个3最终结果：1 → 2 → 3
复杂度分析
• 时间复杂度：O(n) 遍历所有节点
• 空间复杂度：O(n) 递归调用栈深度
注意事项
- 本方法仅适用于已排序的有序链表
- 递归实现方式在长链表时可能引发栈溢出
- 每次递归调用处理当前节点与直接后继节点的关系
- 最终返回的链表保留每个元素的最后一次出现位置
修正记录
原始录音转文字中存在以下修正：
- "驱虫" → "去重"
- "趋同" → "去重"
- "next 的取值" → "next节点的值"
- 修正递归逻辑描述中的顺序问题
- 规范链表节点命名（P → head）
注：根据实际代码逻辑，本实现最终保留的是重复元素的最后一个出现节点。如需保留第一个出现节点，需要调整重复处理逻辑为跳过所有后续重复节点。
基础数据结构-058-链表-e05-有序链表去重1-递归
力扣有序链表去重问题（删除所有重复节点）详解
题目描述
给定一个已排序的链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例
示例1：
输入：1->2->3->3->4->4->5
输出：1->2->5
说明：所有重复的3和4节点均被删除
示例2：
输入：1->1->1->2->3
输出：2->3
说明：所有重复的1节点均被删除
算法分析
与上题区别
• 前序题目：保留重复元素的第一个出现节点
• 本题要求：完全删除所有重复元素（包括原节点）
递归实现思路
边界条件处理：
• 空链表直接返回null• 单节点链表直接返回自身
核心递归逻辑：
• 判断当前节点与下一节点是否重复• 若存在重复：
a. 持续向后遍历直到找到不重复节点
b. 以该不重复节点为起点继续递归
• 若不重复：a. 保留当前节点
b. 递归处理后续节点并更新next指针
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
# 边界条件处理
if not head or not head.next:
return head
# 核心递归逻辑
if head.val == head.next.val:
# 寻找第一个不重复节点
x = head.next.next
while x and x.val == head.val:
x = x.next
# 递归处理后续节点
return self.deleteDuplicates(x)
else:
# 保留当前节点，递归处理后续
head.next = self.deleteDuplicates(head.next)
return head算法验证
测试案例1：
输入：1->2->3->3->4->4->5
处理过程：
- 头节点1与2不重复，保留1，递归处理后续
- 节点2与3不重复，保留2，递归处理后续
- 节点3与下一节点3重复，找到节点4->4->5中的首个不重复节点5
- 最终返回1->2->5
测试案例2：
输入：1->1->1->2->3
处理过程：
- 头节点1与下一节点重复，持续遍历直到找到节点2
- 递归处理节点2，后续无重复
- 最终返回2->3
复杂度分析
• 时间复杂度：O(n)，每个节点最多访问一次
• 空间复杂度：O(n)，递归调用栈空间
关键点总结
- 递归终止条件的正确性
- 重复节点与非重复节点的不同处理逻辑
- 循环查找首个不重复节点的实现
- 递归调用链的正确连接
此算法通过递归方式有效处理了链表节点间的依赖关系，保证了重复元素的完全删除，同时保持了代码的简洁性。
基础数据结构-058-链表-e05-有序链表去重2
链表去重算法详解（非递归实现）
一、数据结构说明
• 哨兵节点：辅助节点，其 next 指针指向链表头节点
• 指针定义：
• p1：指向待删除重复节点的前驱节点
• p2：当前待检测的起始节点
• p3：用于扫描重复节点的移动指针
二、算法思路
边界处理：
• 空链表（head is None）• 单节点链表（
head.next is None）初始化：
dummy = ListNode(0) # 哨兵节点 dummy.next = head p1 = dummy核心逻辑：
while p2 and p3: if p2.val == p3.val: # 发现重复节点 # 移动 p3 直到找到不重复节点 while p3 and p3.val == p2.val: p3 = p3.next # 删除重复节点 p1.next = p3 else: # 无重复则整体后移 p1 = p1.next # 更新检测指针 p2 = p1.next p3 = p2.next if p2 else None
三、完整代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(head):
# 处理边界情况
if not head or not head.next:
return head
# 初始化哨兵节点
dummy = ListNode(0)
dummy.next = head
p1 = dummy
while True:
p2 = p1.next
if not p2: # 已遍历完成
break
p3 = p2.next
if not p3: # 仅剩单个节点无需处理
break
# 检测重复节点
if p2.val == p3.val:
# 移动p3直到非重复节点
while p3 and p3.val == p2.val:
p3 = p3.next
# 删除重复序列
p1.next = p3
else:
# 整体指针后移
p1 = p1.next
return dummy.next四、执行示例
输入链表：1 → 1 → 2 → 3 → 3
处理过程：
- p1(dummy) → p2(1) → p3(1) 检测到重复
- p3 移动到第一个非1节点（值为2）
- p1.next 指向 p3，删除重复的1
- 继续检测后续节点，最终输出：2
五、复杂度分析
• 时间复杂度：O(n)
每个节点最多被访问两次（p2和p3各一次）
• 空间复杂度：O(1)
仅使用固定数量的指针
六、关键点解析
哨兵节点：有效处理头节点可能被删除的情况
三指针协作：
• p1 维护有效链表的尾部• p2 标记当前检测起始点
• p3 扫描重复序列
循环终止条件：当 p2 或 p3 为空时终止扫描
注：本实现可正确处理连续多个重复的情况（如 1→1→1→2→3），且保持算法稳定性。
基础数据结构-058-链表-e06-合并有序链表1
合并有序链表算法详解
问题描述
给定两个按升序排列的链表，要求将其合并为一个新的升序链表。合并后的链表应当包含所有原链表的节点，并保持升序排列。
示例说明
• 输入：
◦ 链表1：1 → 2 → 4
◦ 链表2：1 → 2 → 3
• 输出：
◦ 合并后链表：1 → 1 → 2 → 2 → 3 → 4
• 特殊情况：
◦ 双空链表合并后仍为空
◦ 单空链表直接返回非空链表
算法思路
核心思想
- 使用哨兵节点简化链表头处理
- 双指针遍历两链表，逐个比较节点值
- 动态构建新链表，保持升序排列
- 处理剩余未遍历节点
实现步骤
初始化哨兵节点
s = ListNode() # 哨兵节点 p = s # 新链表指针双指针遍历
p1 = list1 # 链表1指针 p2 = list2 # 链表2指针节点比较与链接
while p1 and p2: if p1.val <= p2.val: p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next # 移动新链表指针处理剩余节点
p.next = p1 if p1 else p2
完整实现代码
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
s = ListNode() # 哨兵节点
p = s # 新链表指针
p1, p2 = list1, list2
# 遍历比较节点
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
# 处理剩余节点
p.next = p1 if p1 else p2
return s.next复杂度分析
• 时间复杂度：O(n+m)
需要遍历两个链表的所有节点
• 空间复杂度：O(1)
仅使用固定数量的指针变量
测试用例
# 示例1
输入：1→2→4, 1→2→3
输出：1→1→2→2→3→4
# 示例2
输入：1→3→8→9, 2→4
输出：1→2→3→4→8→9
# 边界案例
输入：None, None → 输出：None
输入：None, 5→8 → 输出：5→8关键点说明
- 哨兵节点：避免处理空链表的特殊情况
- 双指针遍历：保证线性时间复杂度
- 剩余节点处理：直接链接未遍历完的子链表
- 指针操作：注意指针移动顺序，避免链表断裂
该算法通过巧妙的双指针遍历方式，在保持时间复杂度最优的同时，保证了代码的简洁性和可读性，是处理有序链表合并问题的经典解决方案。
基础数据结构-058-链表-e06-合并有序链表2
合并两个有序链表的递归实现方法详解
一、问题背景
给定两个有序链表：
• 链表1初始状态：1 → 3 → 8 → 9（指针p1）
• 链表2初始状态：2 → 4（指针p2）
要求通过递归方法合并这两个链表，最终形成新的有序链表。
二、递归核心思路
基本逻辑
每次递归操作执行以下三个步骤：比较头节点：比较两个链表当前节点的值
选择较小节点：将较小节点作为当前层递归的返回值
连接后续节点：将选定节点的next指针指向下一层递归结果
终止条件
• 当其中一个链表为空时，直接返回另一个链表
• 递归终止后的连接操作会自动完成剩余节点的拼接
三、递归过程图解
| 递归层级 | 比较对象 | 选择节点 | 剩余链表1 | 剩余链表2 | 后续操作 |
|---|---|---|---|---|---|
| 第一次 | p1(1) vs p2(2) | 1 | 3→8→9 | 2→4 | 将1.next指向后续递归结果 |
| 第二次 | p1(3) vs p2(2) | 2 | 3→8→9 | 4 | 将2.next指向后续递归结果 |
| 第三次 | p1(3) vs p2(4) | 3 | 8→9 | 4 | 将3.next指向后续递归结果 |
| 第四次 | p1(8) vs p2(4) | 4 | 8→9 | null | 将4.next指向后续递归结果 |
| 第五次 | p1(8) vs null | 8 | 9 | null | 将8.next指向后续递归结果 |
最终形成的链表：1 → 2 → 3 → 4 → 8 → 9
四、代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(p1: ListNode, p2: ListNode) -> ListNode:
# 递归终止条件
if not p1:
return p2
if not p2:
return p1
# 比较并选择较小节点
if p1.val < p2.val:
p1.next = mergeTwoLists(p1.next, p2) # 连接后续节点
return p1
else:
p2.next = mergeTwoLists(p1, p2.next) # 连接后续节点
return p2五、算法特性
- 时间复杂度：O(n+m)，遍历两个链表的所有节点
- 空间复杂度：O(n+m)，递归调用栈的深度
- 核心优势：通过递归隐式维护指针，代码简洁直观
六、测试验证
# 构建测试链表
def create_list(arr):
dummy = ListNode()
curr = dummy
for num in arr:
curr.next = ListNode(num)
curr = curr.next
return dummy.next
# 测试用例
list1 = create_list([1, 3, 8, 9])
list2 = create_list([2, 4])
merged = mergeTwoLists(list1, list2)
# 验证输出结果：1 → 2 → 3 → 4 → 8 → 9
while merged:
print(merged.val, end=" → " if merged.next else "")
merged = merged.next基础数据结构-058-链表-e07-合并多个有序链表
合并多个升序链表算法详解
题目描述
输入：包含多个升序链表的数组
输出：将所有链表合并后的单个升序链表
示例：
输入：[1->4->5, 1->3->4, 2->6]
输出：1->1->2->3->4->4->5->6解题思路
分治法（Divide and Conquer）
- 分：将链表数组不断二分，直到每个子数组只剩1个链表
- 治：直接返回单个链表（递归终止条件）
- 合：将两个有序链表合并（基于LeetCode 21题的解法）
递归过程示例
原始数组：[L1, L2, L3, L4, L5]
拆分步骤：
1. 第一次拆分：[L1, L2, L3] 和 [L4, L5]
2. 第二次拆分：[L1, L2] 和 [L3]
3. 合并过程：
- 合并L1和L2得到M1
- 合并M1和L3得到M2
- 合并L4和L5得到M3
- 最终合并M2和M3代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
return self.split(lists, 0, len(lists)-1)
def split(self, lists: List[ListNode], left: int, right: int) -> ListNode:
# 递归终止条件：当区间只剩1个链表
if left == right:
return lists[left]
# 二分区间
mid = (left + right) // 2
# 递归处理左右子区间
l = self.split(lists, left, mid)
r = self.split(lists, mid+1, right)
# 合并两个有序链表
return self.mergeTwoLists(l, r)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next算法分析
时间复杂度
• 每次合并操作时间复杂度为O(N)
• 递归深度为logK（K为链表数量）
• 总时间复杂度：O(NlogK)
空间复杂度
• 递归调用栈深度为logK
• 总空间复杂度：O(logK)
核心概念解析
分而治之（Divide and Conquer）
分：将原问题分解为多个子问题
• 本例中将K个链表拆分为logK层，每层合并操作总时间复杂度O(N)治：解决子问题
• 当子数组只剩单个链表时直接返回合：合并子问题的解
• 使用合并两个有序链表的算法
简而治之（Decrease and Conquer）
• 分治法的特殊形式，每次将问题规模减少而非分割
• 典型应用：二分查找（每次将搜索范围减半）
关键点说明
- 递归终止条件：当链表数组区间缩小到单个元素时直接返回
- 二分策略：通过计算中点索引将数组分为两个子区间
- 合并基础：复用合并两个有序链表的经典解法
- 虚拟头节点：使用dummy节点简化链表合并操作
复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 顺序合并 | O(KN) | O(1) | 链表数量较少时 |
| 分治法合并 | O(NlogK) | O(logK) | 通用最优方案 |
| 优先队列法 | O(NlogK) | O(K) | 适合流式数据输入 |
本解法通过分治策略将问题转化为多个两两合并的子问题，既保证了时间效率，又通过递归实现了代码的简洁性。理解该算法有助于掌握分治思想在链表操作中的典型应用。
基础数据结构-058-链表-e08-查找链表中间节点
力扣题目解析：查找链表的中间节点
题目描述
给定一个单链表的头节点 head，要求返回链表的中间节点。若链表长度为奇数，返回中间节点；若为偶数，返回靠右的中间节点。
示例:
• 奇数长度链表 1 → 2 → 3 → 4 → 5，中间节点为 3。
• 偶数长度链表 1 → 2 → 3 → 4，中间节点为 3（靠右的中间节点）。
解题思路：快慢指针法
通过两个指针（快指针 fast 和慢指针 slow）遍历链表：
- 快指针每次移动两步。
- 慢指针每次移动一步。
- 当快指针到达链表末尾时，慢指针指向中间节点。
原理：快指针的速度是慢指针的两倍。当快指针遍历完链表时，慢指针恰好位于中间位置。
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def middleNode(head: ListNode) -> ListNode:
# 初始化快慢指针均指向头节点
slow = head
fast = head
# 循环条件：快指针及其下一节点均不为空
while fast and fast.next:
slow = slow.next # 慢指针移动一步
fast = fast.next.next # 快指针移动两步
return slow # 返回慢指针指向的中间节点关键步骤解析
指针初始化
•slow和fast初始时均指向头节点head。循环移动指针
• 快指针移动规则：每次移动两步（fast = fast.next.next）。
• 慢指针移动规则：每次移动一步（slow = slow.next）。
• 终止条件：当快指针 fast 为 None 或 fast.next 为 None 时，说明快指针已遍历完链表。
- 中间节点判定
• 循环结束后，慢指针slow指向的节点即为中间节点。
示例验证
示例 1：奇数长度链表
链表 1 → 2 → 3 → 4 → 5：
循环过程：
•slow移动到2，fast移动到3。•
slow移动到3，fast移动到5。终止条件：
fast.next为None，退出循环。结果：
slow指向3。
示例 2：偶数长度链表
链表 1 → 2 → 3 → 4：
循环过程：
•slow移动到2，fast移动到3。•
slow移动到3，fast移动到None（fast.next为4，移动两步后越界）。终止条件：
fast为None，退出循环。结果：
slow指向3。
复杂度分析
• 时间复杂度：O(n)，链表仅遍历一次。
• 空间复杂度：O(1)，仅使用两个指针。
总结
快慢指针法是解决链表中间节点问题的经典方法，通过调整指针步长，确保时间复杂度为 O(n)，空间复杂度为 O(1)。注意循环条件需判断快指针及其下一节点是否为空，避免空指针异常。
基础数据结构-058-链表-e09-判断回文链表1
判断回文链表算法详解
问题描述
给定一个单链表，判断其是否为回文结构。回文链表定义为正序和逆序遍历结果完全相同的链表。
示例
• 有效回文：
• 1→2→2→1（正逆序均为1221）
• 1→2→3→2→1（正逆序均为12321）
• 非回文：
• 1→2（逆序为2→1）
解题思路（时间复杂度O(n)，空间复杂度O(1)）
三步法实现
- 定位中间节点
- 反转后半链表
- 前后半链表逐节点比较
关键步骤图解
原链表：1 → 2 → 2 → 1
中间节点定位：↑（第二个2）
反转后半链表：1 → 2
比较过程：
前半[1,2] vs 后半[1,2] → 匹配算法实现详解
步骤1：快慢指针定位中间节点
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow• 快指针（fast）每次两步，慢指针（slow）每次一步
• 当fast到达末尾时，slow指向中间节点
• 时间复杂度：O(n)
步骤2：反转后半链表
def reverse_list(head):
prev = None
while head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev• 使用三指针法原地反转
• 时间复杂度：O(n)
步骤3：双指针比较
def is_palindrome(head):
# 定位中间节点
mid = find_middle(head)
# 反转后半链表
reversed_half = reverse_list(mid)
# 双指针比较
while reversed_half:
if head.val != reversed_half.val:
return False
head = head.next
reversed_half = reversed_half.next
return True• 比较终止条件：反转后的后半链表遍历完成
• 时间复杂度：O(n)
复杂度分析
| 步骤 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 定位中间节点 | O(n) | O(1) |
| 反转后半链表 | O(n) | O(1) |
| 双指针比较 | O(n) | O(1) |
| 总计 | O(n) | O(1) |
边界测试用例
- 单节点链表：1 → None → True
- 双节点非回文：1 → 2 → False
- 长奇数回文：1→2→3→4→3→2→1 → True
- 长偶数回文：1→2→3→3→2→1 → True
典型错误修正记录
- 原描述"政治读" → 修正为"正着读"
- "O 1的空间复杂" → 修正为"O(1)的空间复杂度"
- "EQ 把它定为简单了" → 修正为"LeetCode标为简单难度"
- 代码变量命名统一化（如prev代替N1）
本方案通过结合快慢指针、链表反转和双指针比较，在保证线性时间复杂度的同时实现常数空间复杂度，是处理回文链表问题的经典解法。
基础数据结构-058-链表-e09-判断回文链表2
回文链表算法优化详解
原方案分析
原方案步骤
- 寻找中间节点：通过快慢指针定位链表中点
- 反转后半链表：将中间节点之后的链表进行反转
- 逐一比较：将反转后的后半链表与原链表前半部分比较
性能问题
• 执行耗时4ms，仅击败80%用户
• 存在两个独立循环（找中点、反转链表）
• 时间复杂度O(n)但常数因子较大
优化方案
核心思路
将寻找中间节点和反转前半链表合并到单个循环中
实现步骤
同步操作阶段：
• 使用快慢指针找中间节点• 在移动慢指针时同步反转前半链表
比较阶段：
• 根据链表长度奇偶性调整比较起始点• 将反转后的前半链表与后半链表比较
代码实现关键点
def isPalindrome(head):
# 初始化指针
new_head = None # 反转后的前半链表头
slow = fast = head
# 同步操作阶段
while fast and fast.next:
fast = fast.next.next
# 反转前半链表
temp = slow.next
slow.next = new_head
new_head = slow
slow = temp
# 处理奇数长度情况
if fast: # 快指针未指向空说明是奇数长度
slow = slow.next
# 比较阶段
while new_head:
if new_head.val != slow.val:
return False
new_head = new_head.next
slow = slow.next
return True优化细节说明
同步反转实现
• 反转逻辑：在慢指针移动时，将节点逐个插入新链表头部
• 指针关系：
• slow：常规慢指针，每次移动一步
• new_head：始终指向反转后的前半链表头部
• temp：临时保存后续节点
奇偶处理机制
• 判断条件：通过快指针是否为空判断链表长度奇偶
• 偶数长度：fast最终指向空
• 奇数长度：fast指向末节点（非空）
• 调整策略：奇数长度时跳过中间节点
性能对比
| 方案 | 时间复杂度 | 空间复杂度 | 执行时间 | 击败比例 |
|---|---|---|---|---|
| 原始方案 | O(n) | O(1) | 4ms | 80% |
| 优化方案 | O(n) | O(1) | 2ms | 100% |
测试用例验证
偶数长度（1221）：
• 前半反转结果：2->1• 后半链表：2->1
• 返回True
奇数长度（12321）：
• 前半反转结果：2->1• 后半链表（调整后）：2->1
• 返回True
非回文（1231）：
• 比较阶段直接返回False
优化总结
- 循环合并：将两个O(n)操作合并到单个循环
- 空间优化：保持O(1)空间复杂度
- 指针操作：通过精确控制指针移动减少冗余操作
- 奇偶处理：通过快指针状态智能判断长度类型
该优化方案通过同步操作和智能指针管理，在保持算法清晰度的同时显著提升执行效率，最终达到最优时间复杂度实现。
基础数据结构-058-链表-e10-判环算法1
以下是整理后的课程文档，已修正错别字并优化表述：
链表环检测算法详解：弗洛伊德龟兔赛跑算法
一、问题描述
检测给定链表中是否存在环形结构。环形链表特征：
- 所有节点的next指针均不为空2.存在至少一个节点可通过连续next访问回到自身形成循环
二、算法原理：弗洛伊德龟兔赛跑算法
阶段一：环存在性检测
算法步骤：
初始化两个指针：
• 慢指针（龟）每次移动1步• 快指针（兔）每次移动2步
同步移动双指针直至：
• 快指针遇到null → 链表无环• 快慢指针相遇 → 链表有环
示例演示：
• 环形链表：龟兔同时从起点出发
• 龟移动路径：1→2→3→4→5...
• 兔移动路径：2→4→6→8→10...
• 最终在节点X相遇（存在环）
• 无环链表：兔会先到达链表尾部（null）
数学原理：
设链表头到环入口距离为A，环周长为B。当龟移动A+NB+K步时，兔移动2(A+N*B+K)步。相遇时满足：
2(A + N*B + K) = A + M*B + K
→ A + K = (M-2N)B阶段二：环入口定位
算法步骤：
阶段一相遇后：
• 重置龟到链表头部• 兔保持相遇位置不变
双指针改为每次各移动1步
再次相遇点即为环入口
数学证明：
• 设头到入口距离A，相遇点到入口距离K
• 由阶段一推导：A = (M-2N)B - K
• 龟从头移动A步到达入口时：
• 兔移动路径：K + A = (M-2N)B → 整数倍环周长，回到入口
三、算法特性
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 检测 | O(n) | O(1) |
| 定位 | O(n) | O(1) |
四、关键结论
- 相遇必然性：环存在时快指针终将追上慢指针
- 入口定位：二次相遇法可精确找到环入口
- 路径关系：头节点到入口距离 = 相遇点到入口距离 + n*环周长
五、扩展思考
• 如何计算环的周长？
• 快指针步长改为3步是否仍有效？
• 该算法在图论中的其他应用场景？
通过该算法可高效解决链表环检测及入口定位问题，兼具理论价值和实践意义。理解其数学本质有助于应对变形问题。
基础数据结构-058-链表-e10-判环算法2
LeetCode 链表环检测问题详解
目录
- LeetCode 141题 - 环形链表检测
- LeetCode 142题 - 环形链表入口检测
- 弗洛伊德龟兔赛跑算法详解
- 测试用例与边界条件分析
- LeetCode 141题 - 环形链表检测
问题描述
给定一个链表，判断链表中是否存在环。
算法思想（弗洛伊德龟兔赛跑算法）
• 双指针策略：使用快慢两个指针（龟指针T、兔指针H）
• 移动规则：
• 龟指针每次移动1步（T = T.next）
• 兔指针每次移动2步（H = H.next.next）
• 终止条件：
• 当两指针相遇时存在环（返回True）
• 当兔指针遇到终点时无环（返回False）
代码实现
def hasCycle(head):
if not head:
return False
H = head # 兔指针
T = head # 龟指针
while H and H.next:
H = H.next.next
T = T.next
if H == T:
return True
return False关键点说明
• 空指针保护：检查H.next存在性避免空指针异常
• 时间复杂度：O(n)，空间复杂度O(1)
- LeetCode 142题 - 环形链表入口检测
问题描述
给定一个可能有环的链表，返回环的入口节点，无环则返回None。
算法思想（两阶段检测）
阶段一：验证环存在性（同141题）
阶段二：
• 龟指针重置到链表头• 两指针同步每次移动1步
• 再次相遇点即为环入口
代码实现
def detectCycle(head):
H = T = head # 初始化龟兔指针
# 阶段一：检测环存在性
has_cycle = False
while H and H.next:
H = H.next.next
T = T.next
if H == T:
has_cycle = True
break
if not has_cycle:
return None
# 阶段二：定位环入口
T = head # 龟指针重置
while True:
if H == T: # 优先检查当前状态
return T
H = H.next
T = T.next关键改进点
• 首尾相连处理：在阶段二开始前优先检查当前状态，避免首尾相连场景误判
• 时间复杂度：保持O(n)时间复杂度
- 弗洛伊德算法数学验证
设链表结构：
• 环外长度：L
• 环周长：C
• 相遇点距入口：X
推导过程：
阶段一相遇时：
• 龟指针移动距离：L + X• 兔指针移动距离：L + X + nC
• 由2(L+X) = L+X+nC → L = nC - X
阶段二移动时：
• 龟指针从起点移动L步到达入口• 兔指针从相遇点移动nC - X步同样到达入口
- 测试用例分析
标准测试案例
# 构造12节点环形链表（入口在N8）
nodes = [ListNode(i) for i in range(1,13)]
for i in range(11):
nodes[i].next = nodes[i+1]
nodes[11].next = nodes[7] # 构造环
print(detectCycle(nodes[0]).val) # 正确输出8边界条件测试
- 首尾相连环：
nodes[11].next = nodes[0] # 尾节点指向头节点
print(detectCycle(nodes[0]).val) # 正确输出1- 单节点环：
single_node = ListNode(1)
single_node.next = single_node
print(detectCycle(single_node).val) # 输出1- 无环链表：
linear_nodes = [ListNode(i) for i in range(5)]
for i in range(4):
linear_nodes[i].next = linear_nodes[i+1]
print(detectCycle(linear_nodes[0])) # 输出None- 其他算法扩展
- 哈希表法：记录访问节点，时间复杂度O(n)，空间复杂度O(n)
- 节点标记法：修改访问过的节点，破坏链表结构
- 长度差值法：通过计算环内外长度定位入口
推荐阅读：《算法导论》图算法章节中的环检测算法分析
基础数据结构-059-数组-e01-合并有序数组1
合并两个有序数组算法详解
问题描述
给定一个数组包含两个有序子区间，要求将这两个有序区间合并为一个整体有序的数组，结果存储在原数组空间。
示例输入：
数组 [1, 5, 6, 2, 4, 10, 11]
第一个有序区间：索引0-2 ([1,5,6])
第二个有序区间：索引3-6 ([2,4,10,11])
预期输出：[1, 2, 4, 5, 6, 10, 11]
方法思路：递归实现
参数说明
void merge(int[] A1, int i, int iEnd, int j, int jEnd, int[] A2, int k)• A1: 原始数组
• i, iEnd: 第一个有序区间的起止索引
• j, jEnd: 第二个有序区间的起止索引
• A2: 存储合并结果的数组（与原数组等长）
• k: 结果数组当前填充位置
算法流程
元素比较
比较两个区间当前元素（A1[i]vsA1[j]）
• 较小者存入A2[k]• 对应区间索引后移（i++或j++）
递归终止条件
• 当某区间元素耗尽时，将另一区间剩余元素整体复制到结果数组if (i > iEnd) { // 第一个区间耗尽 System.arraycopy(A1, j, A2, k, jEnd - j + 1); return; } if (j > jEnd) { // 第二个区间耗尽 System.arraycopy(A1, i, A2, k, iEnd - i + 1); return; }递归调用
每次处理完当前元素后，进行下一层递归if (A1[i] < A1[j]) { A2[k] = A1[i]; merge(A1, i+1, iEnd, j, jEnd, A2, k+1); } else { A2[k] = A1[j]; merge(A1, i, iEnd, j+1, jEnd, A2, k+1); }
完整代码实现
public class MergeSortedArrays {
public static void main(String[] args) {
int[] A1 = {1, 5, 6, 2, 4, 10, 11};
int[] A2 = new int[A1.length];
merge(A1, 0, 2, 3, 6, A2, 0);
// 将结果复制回原数组
System.arraycopy(A2, 0, A1, 0, A2.length);
System.out.println(Arrays.toString(A1)); // [1, 2, 4, 5, 6, 10, 11]
}
static void merge(int[] A1, int i, int iEnd,
int j, int jEnd, int[] A2, int k) {
// 处理区间耗尽的情况
if (i > iEnd) {
System.arraycopy(A1, j, A2, k, jEnd - j + 1);
return;
}
if (j > jEnd) {
System.arraycopy(A1, i, A2, k, iEnd - i + 1);
return;
}
// 比较并递归
if (A1[i] < A1[j]) {
A2[k] = A1[i];
merge(A1, i+1, iEnd, j, jEnd, A2, k+1);
} else {
A2[k] = A1[j];
merge(A1, i, iEnd, j+1, jEnd, A2, k+1);
}
}
}关键点解析
System.arraycopy使用
System.arraycopy(srcArr, srcPos, destArr, destPos, length)高效完成数组复制索引管理
• 递归时严格维护各区间索引边界• 结果数组索引k每次递归+1
空间复杂度
使用与原数组等长的临时数组A2，空间复杂度为O(n)与归并排序的关系
该方法是归并排序的核心合并步骤，时间复杂度为O(n)
示例运行流程
初始状态：
A1: [1,5,6 | 2,4,10,11]
A2: [0,0,0,0,0,0,0]
递归过程：
1. 比较1和2 → 存入1
2. 比较5和2 → 存入2
3. 比较5和4 → 存入4
4. 比较5和10 → 存入5
5. 比较6和10 → 存入6
6. 第一个区间耗尽，复制剩余元素10,11
最终结果：
A2 → [1,2,4,5,6,10,11]基础数据结构-059-数组-e01-合并有序数组2
非递归归并排序实现详解
方法二：非递归实现原理
核心思想
将第一个数组划分为两个有序区间：
• 第一区间元素：[1, 5, 6]
• 第二区间元素：[2, 4, 10, 11]
通过双指针遍历实现合并：
- 定义指针 i/j 分别指向两个有序区间的起始位置（初始值均为0）
- 创建新数组存放合并结果，索引指针 k 初始化为0
- 通过循环比较元素大小，将较小值放入新数组
合并流程示例
| 步骤 | 操作逻辑 | 数组状态变化 |
|---|---|---|
| 1 | 比较 arr1[i=0]=1 和 arr2[j=0]=2 | 新数组插入1，i++ k++ |
| 2 | 比较 arr1[i=1]=5 和 arr2[j=0]=2 | 插入2，j++ k++ |
| 3 | 比较 arr1[i=1]=5 和 arr2[j=1]=4 | 插入4，j++ k++ |
| 4 | 比较 arr1[i=1]=5 和 arr2[j=2]=10 | 插入5，i++ k++ |
| 5 | 比较 arr1[i=2]=6 和 arr2[j=2]=10 | 插入6，i++ k++ |
| 6 | i 越界后处理剩余元素 | 插入10、11 |
代码实现解析
public static void merge(int[] arr1, int[] arr2,
int iStart, int iEnd,
int jStart, int jEnd) {
int i = iStart, j = jStart, k = 0;
// 双指针循环比较
while (i <= iEnd && j <= jEnd) {
if (arr1[i] <= arr1[j]) {
arr2[k++] = arr1[i++];
} else {
arr2[k++] = arr1[j++];
}
}
// 处理剩余元素
if (i > iEnd) {
System.arraycopy(arr1, j, arr2, k, jEnd - j + 1);
} else {
System.arraycopy(arr1, i, arr2, k, iEnd - i + 1);
}
}关键实现细节
循环终止条件：当任一指针超出其区间边界时终止
元素比较逻辑：使用三元运算符优化代码结构
剩余元素处理：
• 使用System.arraycopy批量复制剩余元素• 计算剩余元素长度公式：
区间长度 = 结束索引 - 起始索引 + 1索引管理：
• 每次插入后三个指针同步递增（i/j/k）• 使用后缀自增运算符简化代码
方法对比
| 特性 | 递归版本 | 非递归版本 |
|---|---|---|
| 参数数量 | 包含目标数组索引参数k | 使用局部变量k |
| 空间复杂度 | O(n) | O(n) |
| 代码结构 | 需要递归栈保存状态 | 纯循环结构 |
| 边界处理 | 通过递归终止条件处理 | 显式指针越界判断 |
| 适用场景 | 代码逻辑直观，教学演示 | 实际工程更优，避免栈溢出风险 |
测试验证
- 测试用例输入：
int[] arr1 = {1, 5, 6, 2, 4, 10, 11}; int[] arr2 = new int[7]; - 预期输出：
[1, 2, 4, 5, 6, 10, 11] - 测试方法：
merge(arr1, arr2, 0, 2, 3, 6); System.out.println(Arrays.toString(arr2));
实现要点总结
- 双指针滑动：通过i/j指针实现线性时间复杂度O(n)
- 批量复制优化：减少小元素逐个复制带来的性能损耗
- 边界保护机制：严格校验指针越界条件，保证算法鲁棒性
- 代码简洁性：通过局部变量替代方法参数，提升可维护性
两种实现的核心差异在于状态管理方式，非递归版本通过循环和显式指针控制替代了递归的隐式栈操作，在保持O(n)时间复杂度的同时，避免了递归调用的栈空间开销。
基础数据结构-060-队列-链表实现-1
队列数据结构课程文档
一、队列的定义
队列（Queue）是一种与现实生活中排队场景类似的数据结构，具有以下特性：
• 遵循先进先出（FIFO）原则
• 在一端（尾部）添加数据，在另一端（头部）移除数据
• 与链表的区别：队列只能在固定位置进行添加/删除操作
术语定义：
• 队列尾部（Tail）：数据添加端
• 队列头部（Head）：数据移除端
二、队列接口定义
简化版队列接口（相较于Java原生Queue接口）：
public interface Queue<E> {
// 向队列尾部插入元素
boolean offer(E value);
// 从队列头部移除并返回元素
E poll();
// 查看队列头部元素（不删除）
E peek();
// 判断队列是否为空
boolean isEmpty();
}接口方法说明：
offer(E value)
• 成功插入返回true，失败返回false• 时间复杂度：O(1)
poll()
• 队列非空时返回头部元素并移除• 队列空时返回null
• 时间复杂度：O(1)
peek()
• 仅查看不删除头部元素• 时间复杂度：O(1)
isEmpty()
• 判断队列是否为空
三、链表实现队列
实现方案
采用单向环形带哨兵链表实现：
- 单向：节点仅包含next指针
- 环形：尾节点指向头节点形成闭环
- 带哨兵：简化空队列操作
类结构定义
public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {
private static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
private Node<E> head = new Node<>(null, null);
private Node<E> tail = head;
public LinkedListQueue() {
tail.next = head; // 形成环形结构
}
}方法实现
- offer方法实现
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<>(value, head); // 新节点指向头形成环
tail.next = newNode; // 原尾节点指向新节点
tail = newNode; // 更新尾指针
return true;
}- 迭代器实现
@Override
public Iterator<E> iterator() {
return new Iterator<>() {
Node<E> p = head.next;
@Override
public boolean hasNext() {
return p != head;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}测试用例
public class LinkedListQueueTest {
@Test
public void testOffer() {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
for (Integer value : queue) {
System.out.println(value);
}
// 预期输出：1 2 3 4 5
}
}四、关键实现细节
环形结构维护
• 初始化时tail.next = head• 新增节点时
newNode.next = head哨兵节点作用
• 统一空队列和非空队列的操作逻辑• 避免空指针异常
时间复杂度分析
• 所有操作均保证O(1)时间复杂度• 无循环遍历操作
五、扩展实现方案
数组实现队列
• 使用循环数组结构• 处理数组扩容问题
并发队列
• 线程安全实现• 使用锁或CAS操作
注：本文档已修正原录音中的术语错误（如"poor"修正为"poll"，"prayers"修正为"prev"等），确保技术术语的准确性。