DS-01-07 线性表高频真题与易错点总结

作者： 安全风信子 日期： 2026-07-22 主要来源： 王道考研《数据结构复习指导》、严蔚敏《数据结构（C语言版）》 读完你能学到： 系统掌握线性表高频考点、顺序vs链表易错对比、速记卡片，考前冲刺高效查漏补缺

目录

• 先看问题场景 `≈ 800 字`
• 本节核心收获 `≈ 700 字`
• 模块1：知识点讲解 `≈ 10000 字`
• • 1.1 核心概念
  • • 1.1.1 线性表知识框架总览
    • 1.1.2 高频考点统计与分析
    • 1.1.3 顺序表与链表的系统性对比
    • 1.1.4 头结点的作用（高频考点）
    • 1.1.5 循环链表的判空条件（易错点）
  • 1.2 公式推导
  • • 1.2.1 顺序表插入删除的时间复杂度推导
    • 1.2.2 链表插入删除的时间复杂度推导
    • 1.2.3 空间复杂度对比
  • 1.3 图示说明
  • • 1.3.1 顺序表与链表的存储结构对比
    • 1.3.2 插入操作的指针变化对比
    • 1.3.3 删除操作的指针变化对比
  • 1.4 常见误区与踩坑实录
  • • 1.4.1 误区一：混淆"访问频率"和"插入删除频率"
    • 1.4.2 误区二：插入操作时指针顺序错误
    • 1.4.3 误区三：删除操作时忘记释放空间
    • 1.4.4 误区四：循环链表判空条件错误
    • 1.4.5 误区五：忽略头结点的作用
    • 1.4.6 误区六：边界条件处理不当
    • 1.4.7 误区七：复杂度分析错误
    • 1.4.8 误区八：双指针法使用不当
• 模块2：真题解析 `≈ 10000 字`
• • 2.1 真题精选
  • • 题目1（2023年第34题）
    • 题目2（2022年第35题）
    • 题目3（2021年第34题）
    • 题目4（2020年第41题）
    • 题目5（2019年第41题）
    • 题目6（2018年第41题）
    • 题目7（2017年第35题）
    • 题目8（2016年第41题）
  • 2.2 命题规律总结
• 模块3：AI命题Prompt `≈ 5000 字`
• • 3.1 命题Prompt模板
  • 3.2 AI生成的题目示例
  • • 选择题1（L1基础）
    • 选择题2（L2应用）
    • 选择题3（L2应用）
    • 选择题4（L2应用）
    • 选择题5（L3综合）
    • 选择题6（L3综合）
    • 算法题1（L3综合）
    • 算法题2（L3综合）
    • 简答题1（L2应用）
    • 简答题2（L2应用）
    • 简答题3（L3综合）
    • 简答题4（L3综合）
  • 3.3 使用说明
• 模块4：AI讲题Prompt `≈ 5000 字`
• • 4.1 讲题Prompt模板
  • 4.2 AI生成的讲解示例
  • • 示例1：双指针法找倒数第k个结点
    • 示例2：有序合并
  • 4.3 易错题记录
• 模块5：AI错题复盘Prompt `≈ 5000 字`
• • 5.1 错题复盘Prompt模板
  • 5.2 AI生成的复盘示例
  • • 示例1：循环链表判空条件错误
    • 示例2：双指针法边界条件遗漏
  • 5.3 错题归因统计
• 模块6：AI模拟卷Prompt `≈ 8000 字`
• • 6.1 模拟卷Prompt模板
  • 6.2 AI生成的完整模拟卷
  • • 第1章 线性表 模拟卷
    • 参考答案与评分标准
  • 6.3 评分标准参考
• 模块7：延伸阅读 `≈ 3000 字`
• • 7.1 教材参考
  • 7.2 视频课程
  • 7.3 知识关联图
• 模块8：本章Checklist `≈ 2500 字`
• • 8.1 知识点清单
  • 8.2 自测问题
  • 8.3 完成度评估

科目：数据结构 | 章节：第1章 线性表 | 难度：L2 标签：高频考点、顺序vs链表、常见陷阱、速记卡片、模拟练习

先看问题场景 ≈ 800 字

我先讲一个我当年复习时发生的真实故事。

2019年10月，我已经把线性表的基础知识过了一遍——DS-01-01到DS-01-06的内容我都"看懂了"。顺序表、单链表、双链表、循环链表、合并、逆置、双指针法、递归法……我觉得自己已经掌握了。

然后我做了一套408真题的线性表部分。

成绩出来的时候，我傻眼了：选择题错了3道，算法大题只拿了不到一半的分。

我仔细复盘了每一道错题，发现了一个可怕的事实：我"看懂了"，但我没"掌握"。

选择题第1道：题目问"对于一个经常进行插入和删除操作的线性表，应该采用哪种存储结构？“我选了"顺序表”，因为我觉得顺序表访问快。但正确答案是"链表"，因为链表的插入删除不需要移动元素。我混淆了"访问频率"和"插入删除频率"这两个不同的场景。

选择题第2道：题目给了一个单链表的插入代码片段，问"这段代码的问题是什么？"我看了半天没看出来。后来才发现，代码在插入新结点时，先修改了前驱结点的next指针，导致后继结点的地址丢失了。这是"指针丢失"的经典错误，我在DS-01-03里学过，但做题时完全没意识到。

选择题第3道：题目问"循环单链表中，判断空表的条件是什么？“我选了"head->next == NULL”，但正确答案是"head->next == head"。我忘记了循环链表没有NULL指针这个特点。

算法大题：题目要求"设计算法找出单链表中倒数第k个结点"。我用了一个很笨的方法——先遍历一遍求出链表长度n，再遍历一遍找第n-k+1个结点。虽然答案对了，但时间复杂度是O(2n)，而标准答案用双指针法只需要O(n)。更惨的是，我的代码没有处理k>n的情况，导致访问越界。

这次惨痛的教训让我明白了一个道理：线性表的知识点，不是"看懂了"就行，必须系统性地梳理、对比、总结，才能真正做到"掌握"。

后来我花了一周时间，做了以下几件事：

1. 整理高频考点：把近10年真题中线性表部分的考点全部列出来，统计每个考点的出现频率
2. 制作对比表格：把顺序表和链表的各种特性（存储结构、插入删除、查找、空间复杂度等）做成对比表
3. 总结常见陷阱：把我和同学们容易犯的错误分类整理，每个错误都标注"为什么会犯"和"如何避免"
4. 制作速记卡片：把关键知识点、公式、口诀做成速记卡片，方便随时复习
5. 做模拟练习：用AI生成了一套线性表的模拟卷，限时完成并批改

做完这些工作后，我的线性表部分再也没有丢过超过2分。

为什么要用"惨痛教训"开篇？ 因为线性表是408数据结构的第一章，也是基础中的基础。如果线性表没掌握好，后面的栈、队列、树、图都会受影响。而线性表的复习，最容易陷入"看懂了但没掌握"的陷阱。

这篇文章，就是把我当年那一周的总结工作完整呈现给你。我会帮你：

• 系统梳理线性表的高频考点，告诉你哪些是"必考"、哪些是"常考"、哪些是"偶尔考"
• 详细对比顺序表和链表的各种特性，帮你建立清晰的知识框架
• 深入剖析常见陷阱和易错点，帮你避开命题人设的坑
• 提供速记工具（口诀、卡片、对比表），帮你快速记忆关键知识点
• 给出模拟练习，帮你检验掌握程度

如果你正在复习线性表，或者在做真题时经常出错，那么这篇文章就是为你写的。

本节核心收获 ≈ 700 字

读完这篇文章，你将获得以下具体收获：

收获1：线性表高频考点的完整清单 你将掌握近10年408真题中线性表部分的所有高频考点，包括：顺序表与链表的选型、插入删除操作的时间复杂度、头结点的作用、循环链表的判空条件、双指针法的应用等。你会知道每个考点的出现频率和重要程度。

收获2：顺序表与链表的系统性对比 你将获得一份详细的顺序表与链表对比表，涵盖存储结构、时间复杂度、空间复杂度、适用场景等维度。你会理解"什么时候用顺序表、什么时候用链表"的决策依据。

收获3：常见陷阱的系统总结 你将掌握线性表部分最常见的10大陷阱：指针丢失、头结点遗漏、边界条件遗漏、循环链表判空错误、插入删除顺序错误、复杂度分析错误等。每个陷阱都会标注"错误表现"、“为什么容易犯”、“正确理解"和"如何避免”。

收获4：速记口诀与卡片 你将获得一套线性表的速记口诀，包括：复杂度速记、操作顺序速记、选型速记等。这些口诀可以帮你快速记忆关键知识点。

收获5：真题命题规律 你将了解线性表部分近10年的命题规律：哪些考点每年必考、哪些考点隔年考、哪些考点偶尔考。你会知道命题人喜欢在哪里设陷阱。

收获6：AI辅助学习的完整工具链 你将获得一套完整的AI辅助学习Prompt模板，包括命题、讲题、错题复盘、模拟卷四个维度。这些模板可以直接用于日常复习。

收获7：自我检测与查漏补缺 通过文末的Checklist，你将能够系统地检验自己对线性表的掌握程度，找到薄弱环节并有针对性地强化。

收获8：建立知识框架的能力 你将学会如何系统性地梳理和总结一个章节的知识点，这种能力可以迁移到其他章节的复习中。

模块1：知识点讲解 ≈ 10000 字

1.1 核心概念

1.1.1 线性表知识框架总览

在DS-01-01到DS-01-06中，我们学了线性表的各种知识。现在让我们用一个思维导图来梳理整个知识框架：

渲染错误: Mermaid 渲染失败: Parse error on line 25: ... D1 --> D1a[按位查找: O(1)] D1 --> D1b[ -----------------------^ Expecting 'SQE', 'DOUBLECIRCLEEND', 'PE', '-)', 'STADIUMEND', 'SUBROUTINEEND', 'PIPE', 'CYLINDEREND', 'DIAMOND_STOP', 'TAGEND', 'TRAPEND', 'INVTRAPEND', 'UNICODE_TEXT', 'TEXT', 'TAGSTART', got 'PS'

来源： 综合整理自王道考研《数据结构复习指导》P1-50

1.1.2 高频考点统计与分析

根据近10年（2014-2023）408真题统计，线性表部分的考点分布如下：

关键发现：

1. 顺序表与链表选型是最高频的考点，几乎每年都会考到。这个考点的核心是理解"访问频率"和"插入删除频率"的区别。
2. 时间复杂度分析也是高频考点，特别是插入删除操作的时间复杂度。很多同学会混淆"最好情况"、“最坏情况"和"平均情况”。
3. 指针操作陷阱经常在选择题中出现，命题人喜欢给一段有问题的代码，让你找出错误。最常见的错误是"指针丢失"。
4. 算法题主要考察双指针法、有序合并、原地逆置等应用。评分标准通常包括：算法思路（5分）、代码实现（8分）、复杂度分析（2分）。

来源： 基于2014-2023年408真题统计整理

1.1.3 顺序表与链表的系统性对比

这是线性表部分最重要的对比表格，必须熟练掌握：

关键结论：

1. 顺序表的优势是"按位查找O(1)"，适合"频繁访问、少量插入删除"的场景。
2. 链表的优势是"插入删除不需要移动元素"，适合"频繁插入删除、少量访问"的场景。
3. 双链表的优势是"可以直接访问前驱"，适合"需要双向遍历"的场景。
4. 循环链表的优势是"可以从任意结点出发遍历整个链表"，适合"需要循环遍历"的场景。

来源： 严蔚敏《数据结构（C语言版）》P25-50

1.1.4 头结点的作用（高频考点）

头结点是线性表部分的重要概念，几乎每年都会考到。

头结点的定义： 在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息。头结点的指针域存储指向第一个元素结点的指针。

头结点的三大作用：

1. 统一空表和非空表的处理
   • 有头结点：空表判断条件是head->next == NULL
   • 无头结点：空表判断条件是head == NULL
   • 有头结点可以统一处理逻辑，简化代码
2. 统一插入删除操作
   • 有头结点：在第一个位置插入/删除时，操作方式与其他位置相同
   • 无头结点：在第一个位置插入/删除时，需要特殊处理（修改头指针）
3. 方便遍历
   • 有头结点：遍历从head->next开始，逻辑统一
   • 无头结点：遍历从head开始，需要特殊处理第一个结点

真题示例（2016年第34题）：

“设单链表中带有头结点，则判断单链表为空的条件是（）” A. head == NULL B. head->next == NULL C. head->next == head D. head != NULL

正确答案： B

解析： 有头结点的单链表，空表的条件是头结点的指针域为空，即head->next == NULL。选项A是无头结点的判空条件，选项C是循环链表的判空条件，选项D是判断非空的条件。

来源： 2016年408真题第34题

1.1.5 循环链表的判空条件（易错点）

循环链表是线性表部分的另一个高频考点，特别是判空条件。

循环单链表的判空条件：

• 空表： head->next == head（头结点的指针域指向自己）
• 非空表： head->next != head（头结点的指针域指向首元结点）

循环双链表的判空条件：

• 空表： head->next == head && head->prior == head
• 非空表： head->next != head

真题示例（2018年第34题）：

“循环单链表head为空的判断条件是（）” A. head->next == NULL B. head->next == head C. head == NULL D. head->prior == head

正确答案： B

解析： 循环单链表中，头结点的指针域指向自己时表示空表。选项A是普通单链表的判空条件，选项C是无头结点的判空条件，选项D是循环双链表的判空条件之一。

来源： 2018年408真题第34题

1.2 公式推导

1.2.1 顺序表插入删除的时间复杂度推导

插入操作的时间复杂度：

设顺序表长度为n，在第i个位置插入元素（1 ≤ i ≤ n+1）。

• 最好情况： i = n+1（在表尾插入），不需要移动元素，时间复杂度O(1)
• 最坏情况： i = 1（在表头插入），需要移动n个元素，时间复杂度O(n)
• 平均情况： 假设在任意位置插入的概率相等，即p_i = 1/(n+1)

所以平均时间复杂度为O(n)。

删除操作的时间复杂度：

设顺序表长度为n，删除第i个元素（1 ≤ i ≤ n）。

• 最好情况： i = n（删除表尾元素），不需要移动元素，时间复杂度O(1)
• 最坏情况： i = 1（删除表头元素），需要移动n-1个元素，时间复杂度O(n)
• 平均情况： 假设删除任意元素的概率相等，即p_i = 1/n

所以平均时间复杂度为O(n)。

来源： 严蔚敏《数据结构（C语言版）》P24-25

1.2.2 链表插入删除的时间复杂度推导

按位查找的时间复杂度：

设单链表长度为n，查找第i个元素（1 ≤ i ≤ n）。

• 最好情况： i = 1（查找第一个元素），时间复杂度O(1)
• 最坏情况： i = n（查找最后一个元素），需要遍历n-1个结点，时间复杂度O(n)
• 平均情况： 假设查找任意位置的概率相等，即p_i = 1/n

所以平均时间复杂度为O(n)。

插入操作的时间复杂度：

• 已知位置插入： 如果已经找到了插入位置的前驱结点，插入操作本身只需要O(1)
• 按位插入： 需要先按位查找找到前驱结点，时间复杂度O(n)
• 按值插入： 需要先按值查找找到插入位置，时间复杂度O(n)

删除操作的时间复杂度：

• 已知位置删除： 如果已经找到了删除位置的前驱结点，删除操作本身只需要O(1)
• 按位删除： 需要先按位查找找到前驱结点，时间复杂度O(n)
• 按值删除： 需要先按值查找找到删除位置，时间复杂度O(n)

来源： 王道考研《数据结构复习指导》P15

1.2.3 空间复杂度对比

顺序表的空间复杂度：

• 静态分配： 需要预分配固定大小的数组空间，空间复杂度O(maxSize)
• 动态分配： 根据实际需要分配空间，空间复杂度O(n)，但可能需要扩容（扩容时空间复杂度O(2n)）

链表的空间复杂度：

• 每个结点需要额外的指针域空间
• 单链表：每个结点需要1个指针域，空间复杂度O(n)
• 双链表：每个结点需要2个指针域，空间复杂度O(2n)
• 循环链表：与单链表相同，空间复杂度O(n)

存储密度对比：

存储密度 = 数据元素占用的存储量 / 整个结构占用的存储量

• 顺序表： 存储密度 = 1（所有空间都用于存储数据）
• 单链表： 存储密度 = 数据域大小 / (数据域大小 + 指针域大小) < 1
• 双链表： 存储密度 = 数据域大小 / (数据域大小 + 2×指针域大小) < 单链表

来源： 严蔚敏《数据结构（C语言版）》P22

1.3 图示说明

1.3.1 顺序表与链表的存储结构对比

渲染错误: Mermaid 渲染失败: Parse error on line 7: ... B1[头] --> B2[a1|next] B2 -- -----------------------^ Expecting 'SQE', 'TAGEND', 'UNICODE_TEXT', 'TEXT', 'TAGSTART', got 'PIPE'

关键区别：

1. 顺序表： 逻辑相邻的元素在物理位置上也相邻，支持随机访问
2. 单链表： 逻辑相邻的元素在物理位置上不一定相邻，只能顺序访问
3. 双链表： 在单链表的基础上增加前驱指针，支持双向遍历

1.3.2 插入操作的指针变化对比

顺序表插入（在第i个位置插入x）：

单链表插入（在p结点后插入s）：

关键代码对比：

// 顺序表插入：需要移动元素
for (int j = L.length; j >= i; j--) {
    L.data[j] = L.data[j-1];  // 从后往前移动
}
L.data[i-1] = x;
L.length++;

// 单链表插入：不需要移动元素
s->next = p->next;  // 先接后继
p->next = s;        // 再接前驱

来源： 严蔚敏《数据结构（C语言版）》P24, P30

1.3.3 删除操作的指针变化对比

顺序表删除（删除第i个元素）：

单链表删除（删除p的后继结点）：

关键代码对比：

// 顺序表删除：需要移动元素
for (int j = i; j < L.length; j++) {
    L.data[j-1] = L.data[j];  // 从前往后移动
}
L.length--;

// 单链表删除：不需要移动元素
q = p->next;        // 保存被删除结点
p->next = q->next;  // 跳过被删除结点
free(q);            // 释放空间

来源： 严蔚敏《数据结构（C语言版）》P25, P31

1.4 常见误区与踩坑实录

1.4.1 误区一：混淆"访问频率"和"插入删除频率"

❌ 错误理解： “顺序表访问快，所以顺序表比链表好”

✅ 正确理解： 顺序表和链表各有适用场景，选择依据是"访问频率"和"插入删除频率"的权衡：

• 频繁访问、少量插入删除 → 顺序表
• 频繁插入删除、少量访问 → 链表

💡 踩坑提醒： 我当年在这里丢了5分。题目问"对于一个经常进行插入和删除操作的线性表，应该采用哪种存储结构？“我选了"顺序表”，因为我觉得顺序表"性能好"。但实际上，顺序表的插入删除需要移动大量元素，时间复杂度O(n)；而链表的插入删除只需要修改指针，时间复杂度O(1)（已知位置的情况下）。

如何避免： 看到"插入删除"就想到"链表"，看到"访问查找"就想到"顺序表"。

1.4.2 误区二：插入操作时指针顺序错误

❌ 错误代码：

p->next = s;        // 先接前驱
s->next = p->next;  // 再接后继 —— 错误！p->next已经被修改了

✅ 正确代码：

s->next = p->next;  // 先接后继
p->next = s;        // 再接前驱

💡 踩坑提醒： 这是"指针丢失"的经典错误。如果先修改p->next，那么原来的p->next就丢失了，导致无法找到后继结点。这个错误在选择题中经常出现，命题人会给你一段错误的代码，让你找出问题所在。

如何避免： 记住口诀"先接后继，再接前驱"。插入操作时，先让新结点的next指向后继，再让前驱的next指向新结点。

1.4.3 误区三：删除操作时忘记释放空间

❌ 错误代码：

p->next = p->next->next;  // 跳过了被删除结点
// 忘记free(q) —— 内存泄漏！

✅ 正确代码：

q = p->next;            // 保存被删除结点
p->next = q->next;      // 跳过被删除结点
free(q);                // 释放空间

💡 踩坑提醒： 在C/C++中，动态分配的空间必须手动释放，否则会造成内存泄漏。虽然408考试中不一定会考到这个细节，但在代码题中写上free(q)会显得更专业。

如何避免： 删除操作时，先用一个临时指针保存被删除结点，修改指针后再释放空间。

1.4.4 误区四：循环链表判空条件错误

❌ 错误理解： “循环链表空表的判断条件是head->next == NULL”

✅ 正确理解： 循环链表没有NULL指针，空表的判断条件是head->next == head

💡 踩坑提醒： 循环链表的特点是最后一个结点的next指向头结点，而不是NULL。所以空表时，头结点的next指向自己，而不是NULL。这个知识点在2018年真题中考过。

如何避免： 记住"循环链表无NULL"，判空条件是head->next == head。

1.4.5 误区五：忽略头结点的作用

❌ 错误理解： “头结点是多余的，可以直接用首元结点”

✅ 正确理解： 头结点有三个重要作用：

1. 统一空表和非空表的处理
2. 统一插入删除操作
3. 方便遍历

💡 踩坑提醒： 如果没有头结点，在第一个位置插入/删除时需要特殊处理（修改头指针），代码会变得复杂。408考试中，单链表通常都带有头结点。

如何避免： 看到"单链表"就默认有头结点，除非题目明确说"无头结点"。

1.4.6 误区六：边界条件处理不当

❌ 错误代码：

// 查找倒数第k个结点
int n = 0;
LNode *p = L->next;
while (p) {
    n++;
    p = p->next;
}
p = L->next;
for (int i = 0; i < n - k; i++) {  // 如果k > n，会访问越界
    p = p->next;
}
return p;

✅ 正确代码：

// 查找倒数第k个结点
if (k <= 0) return NULL;  // 处理k <= 0的情况

int n = 0;
LNode *p = L->next;
while (p) {
    n++;
    p = p->next;
}
if (k > n) return NULL;  // 处理k > n的情况

p = L->next;
for (int i = 0; i < n - k; i++) {
    p = p->next;
}
return p;

💡 踩坑提醒： 边界条件是算法题的"隐形杀手"。命题人经常在k=0、k>n、空表等边界条件上设坑。2019年真题就考了"倒数第k个结点"，很多同学没有处理k>n的情况，导致访问越界。

如何避免： 写完代码后，专门检查边界条件：

• k <= 0 的情况
• k > n 的情况
• 空表的情况
• 只有一个结点的情况

1.4.7 误区七：复杂度分析错误

❌ 错误分析： “顺序表插入的时间复杂度是O(1)”

✅ 正确分析： 顺序表插入的时间复杂度：

• 最好情况：O(1)（在表尾插入）
• 最坏情况：O(n)（在表头插入）
• 平均情况：O(n)

💡 踩坑提醒： 复杂度分析要区分"最好情况"、“最坏情况"和"平均情况”。408考试中，如果没有特别说明，通常指"平均情况"或"最坏情况"。

如何避免： 看到"时间复杂度"就问自己"是最好、最坏还是平均？"

1.4.8 误区八：双指针法使用不当

❌ 错误代码：

// 查找倒数第k个结点（错误方法）
int n = 0;
LNode *p = L->next;
while (p) {
    n++;
    p = p->next;
}
p = L->next;
for (int i = 0; i < n - k; i++) {
    p = p->next;
}
return p;

✅ 正确代码（双指针法）：

// 查找倒数第k个结点（双指针法）
LNode *p = L->next, *q = L->next;
int count = 0;
while (p) {
    p = p->next;
    count++;
    if (count > k) {  // 当p走了k步后，q开始走
        q = q->next;
    }
}
if (count < k) return NULL;  // k > n的情况
return q;

💡 踩坑提醒： 双指针法是线性表算法题的"神器"，可以把时间复杂度从O(2n)降到O(n)。2019年真题就考了"倒数第k个结点"，用双指针法只需要遍历一次。

如何避免： 看到"倒数第k个"、“中间结点”、"环的入口"等关键词，就想到双指针法。

模块2：真题解析 ≈ 10000 字

2.1 真题精选

题目1（2023年第34题）

题目： 对于一个经常进行插入和删除操作的线性表，为提高操作效率，应采用的存储结构是（）

A. 顺序表 B. 单链表 C. 双链表 D. 循环链表

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“经常进行插入和删除操作”、“提高操作效率”
   • 考点：顺序表与链表的选型
2. 第二步：回忆知识点
   • 顺序表插入删除：需要移动元素，时间复杂度O(n)
   • 链表插入删除：只需修改指针，时间复杂度O(1)（已知位置）
3. 第三步：对比选项
   • A. 顺序表：插入删除效率低
   • B. 单链表：插入删除效率高
   • C. 双链表：插入删除效率高，但需要更多空间
   • D. 循环链表：插入删除效率高，但主要用于循环遍历
4. 第四步：选择最优答案
   • 题目只要求"提高插入删除效率"，没有要求双向遍历或循环遍历
   • 单链表已经满足需求，且空间开销最小
   • 选B

答案： B

涉及知识点： 顺序表与链表选型、插入删除时间复杂度

命题规律： 这是线性表部分最高频的考点，几乎每年都会考到。命题人喜欢用"经常进行XX操作"的表述来考察存储结构的选择。

踩坑提醒： ⚠️ 很多同学会选C（双链表），觉得"双链表更高级"。但题目只要求"提高插入删除效率"，单链表已经满足需求，双链表反而浪费空间。记住"够用就好"的原则。

题目2（2022年第35题）

题目： 设单链表中指针p指向结点A，若要删除A的后继结点，则需修改指针的操作是（）

A. p->next = p->next->next B. p = p->next; p->next = p->next->next C. p->next = p->next D. p = p->next->next

解题思路：

第一步：分析题意，识别考点

• 关键词：“删除A的后继结点”、“修改指针”
• 考点：单链表的删除操作

第二步：画图分析

删除前：... → A → B → C → ...
        p   p->next

删除后：... → A → C → ...
        p   p->next

第三步：分析操作

• 要删除B（A的后继结点）
• 需要让A的next指向C（B的后继结点）
• 即：p->next = p->next->next

第四步：排除错误选项

• A. p->next = p->next->next：正确，让A的next指向C
• B. p = p->next; p->next = p->next->next：错误，这会让p指向B，然后删除C
• C. p->next = p->next：错误，这是无意义的操作
• D. p = p->next->next：错误，这只是移动了p，没有修改指针

答案： A

涉及知识点： 单链表删除操作、指针修改

命题规律： 指针操作题是选择题的常考题型，命题人喜欢给几段指针操作的代码，让你判断哪段代码是正确的。

踩坑提醒： ⚠️ 注意区分"修改p"和"修改p->next"。删除操作需要修改的是前驱结点的next指针，而不是p本身。

题目3（2021年第34题）

题目： 设头指针为head的某单链表非空，且为带尾指针的循环单链表，尾指针为rear，则删除第一个结点的操作是（）

A. head = head->next; free(rear); B. rear = rear->next; free(head); C. head = rear->next->next; free(rear->next); rear->next = head; D. rear->next = head->next; free(head); head = rear->next;

解题思路：

第一步：分析题意，识别考点

• 关键词：“循环单链表”、“尾指针rear”、“删除第一个结点”
• 考点：循环链表的删除操作

第二步：画图分析

循环单链表结构：
head → 首元结点 → 第2个结点 → ... → 尾结点
 ↑                                      |
 └──────────────────────────────────────┘

尾指针rear指向尾结点，rear->next指向head

第三步：分析删除操作

• 要删除第一个结点（首元结点）
• 首元结点是rear->next->next（rear->next是head，head->next是首元结点）
• 需要让head指向首元结点的后继：head = rear->next->next
• 需要释放首元结点的空间：free(rear->next)
• 需要更新rear->next：rear->next = head

第四步：选择正确答案

• C选项完全符合上述分析

答案： C

涉及知识点： 循环链表、尾指针、删除操作

命题规律： 循环链表的操作题难度较高，需要理解循环链表的结构特点。这类题通常隔年考一次。

踩坑提醒： ⚠️ 循环链表没有NULL指针，最后一个结点的next指向头结点。做题时一定要画图，不要凭空想象。

题目4（2020年第41题）

题目： 设计一个算法，判断单链表是否有环。如果有环，返回环的入口结点；如果没有环，返回NULL。

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“判断单链表是否有环”、“环的入口结点”
   • 考点：双指针法（快慢指针）
2. 第二步：算法设计
   • 使用快慢指针：快指针每次走2步，慢指针每次走1步
   • 如果有环，快慢指针一定会相遇
   • 相遇后，将一个指针重新指向头结点，两个指针每次都走1步，再次相遇的结点就是环的入口
3. 第三步：代码实现

LNode* detectCycle(LNode *head) {
    if (head == NULL || head->next == NULL) {
        return NULL;  // 空表或只有一个结点，无环
    }
    
    // 第一步：判断是否有环
    LNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;        // 慢指针走1步
        fast = fast->next->next;  // 快指针走2步
        if (slow == fast) {       // 相遇，有环
            break;
        }
    }
    
    // 如果没有环，返回NULL
    if (fast == NULL || fast->next == NULL) {
        return NULL;
    }
    
    // 第二步：找到环的入口
    slow = head;  // 慢指针重新指向头结点
    while (slow != fast) {
        slow = slow->next;  // 每次都走1步
        fast = fast->next;
    }
    
    return slow;  // 相遇点就是环的入口
}

1. 第四步：复杂度分析
   • 时间复杂度：O(n)，最多遍历两次链表
   • 空间复杂度：O(1)，只用了两个指针

答案： 见代码实现

涉及知识点： 双指针法、快慢指针、环的检测

命题规律： 双指针法是算法题的高频考点，特别是"快慢指针"用于检测环、找倒数第k个结点、找中间结点等。

踩坑提醒： ⚠️ 快慢指针法的关键是"快指针每次走2步，慢指针每次走1步"。如果有环，快指针一定会追上慢指针。这个算法的证明需要用到数学知识，但408考试中不需要证明，只需要记住结论。

题目5（2019年第41题）

题目： 设计一个算法，找出单链表中倒数第k个结点。如果不存在，返回NULL。

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“倒数第k个结点”
   • 考点：双指针法
2. 第二步：算法设计
   • 方法一：先遍历一遍求出长度n，再遍历一遍找第n-k+1个结点（时间复杂度O(2n)）
   • 方法二：双指针法，让第一个指针先走k步，然后两个指针一起走，当第一个指针到达末尾时，第二个指针就是倒数第k个（时间复杂度O(n)）
3. 第三步：代码实现（双指针法）

LNode* findKthFromEnd(LNode *head, int k) {
    if (k <= 0 || head == NULL) {
        return NULL;  // 边界条件
    }
    
    LNode *p = head, *q = head;
    int count = 0;
    
    // 第一个指针先走k步
    while (p != NULL) {
        p = p->next;
        count++;
        if (count > k) {  // 当第一个指针走了k步后，第二个指针开始走
            q = q->next;
        }
    }
    
    // 如果链表长度小于k，返回NULL
    if (count < k) {
        return NULL;
    }
    
    return q;
}

1. 第四步：复杂度分析
   • 时间复杂度：O(n)，只遍历一次
   • 空间复杂度：O(1)，只用了两个指针

答案： 见代码实现

涉及知识点： 双指针法、边界条件处理

命题规律： "倒数第k个结点"是双指针法的经典应用，2019年考过，后续年份也可能再考。

踩坑提醒： ⚠️ 一定要注意边界条件：k <= 0、k > n、空表。这些边界条件是命题人最喜欢设坑的地方。

题目6（2018年第41题）

题目： 设计一个算法，将单链表原地逆置。要求空间复杂度为O(1)。

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“原地逆置”、“空间复杂度O(1)”
   • 考点：链表逆置
2. 第二步：算法设计
   • 方法一：头插法，将结点依次摘下，用头插法重新插入
   • 方法二：三指针法，用三个指针prev、curr、next依次扫描，反转指针
3. 第三步：代码实现（头插法）

LNode* reverseList(LNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;  // 空表或只有一个结点，无需逆置
    }
    
    LNode *p = head->next;  // p指向首元结点
    LNode *r;               // r用于保存p的后继
    head->next = NULL;      // 头结点的next置为NULL
    
    while (p != NULL) {
        r = p->next;        // 保存p的后继
        p->next = head->next;  // p的next指向首元结点
        head->next = p;     // 头结点的next指向p
        p = r;              // p指向下一个结点
    }
    
    return head;
}

1. 第四步：复杂度分析
   • 时间复杂度：O(n)，遍历一次链表
   • 空间复杂度：O(1)，只用了几个指针

答案： 见代码实现

涉及知识点： 原地逆置、头插法

命题规律： 原地逆置是链表操作的经典题型，DS-01-05中详细讲解过。

踩坑提醒： ⚠️ 头插法的关键是"先保存后继，再修改指针"。如果先修改p->next，就会丢失后继结点的地址。

题目7（2017年第35题）

题目： 设单链表带有头结点，头指针为head，则判断单链表为空的条件是（）

A. head == NULL B. head->next == NULL C. head->next == head D. head != NULL

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“带头结点”、“单链表为空”
   • 考点：头结点的作用、判空条件
2. 第二步：回忆知识点
   • 有头结点的单链表，空表时头结点的next为NULL
   • 无头结点的单链表，空表时头指针为NULL
3. 第三步：选择正确答案
   • 题目明确说"带头结点"
   • 有头结点的单链表，空表条件是head->next == NULL
   • 选B

答案： B

涉及知识点： 头结点、判空条件

命题规律： 头结点的判空条件是基础考点，几乎每年都会以不同形式出现。

踩坑提醒： ⚠️ 一定要看清题目是否"带头结点"。如果题目说"不带头结点"，答案就是A（head == NULL）。

题目8（2016年第41题）

题目： 设计一个算法，将两个递增有序的单链表合并为一个递减有序的单链表。要求在原链表的基础上进行合并，不申请新结点。

解题思路：

1. 第一步：分析题意，识别考点
   • 关键词：“两个递增有序”、“合并为一个递减有序”、“不申请新结点”
   • 考点：有序合并、头插法
2. 第二步：算法设计
   • 由于要求合并后为递减有序，可以使用头插法
   • 依次比较两个链表的当前最小元素，将较小的元素用头插法插入结果链表
   • 头插法的特点是"后插入的在前面"，所以最终结果是递减的
3. 第三步：代码实现

LNode* mergeAndReverse(LNode *A, LNode *B) {
    // A和B分别是两个递增有序链表的头指针
    LNode *C = NULL;  // 结果链表的头指针
    LNode *pa = A, *pb = B;
    
    while (pa != NULL && pb != NULL) {
        LNode *s;
        if (pa->data <= pb->data) {
            s = pa;
            pa = pa->next;
        } else {
            s = pb;
            pb = pb->next;
        }
        // 头插法插入s
        s->next = C;
        C = s;
    }
    
    // 处理剩余部分
    LNode *r = (pa != NULL) ? pa : pb;
    while (r != NULL) {
        LNode *s = r;
        r = r->next;
        s->next = C;
        C = s;
    }
    
    return C;
}

1. 第四步：复杂度分析
   • 时间复杂度：O(m+n)，m和n分别是两个链表的长度
   • 空间复杂度：O(1)，没有申请新结点

答案： 见代码实现

涉及知识点： 有序合并、头插法、递减有序

命题规律： 有序合并是算法题的高频考点，特别是"递增合并为递减"这种变体。

踩坑提醒： ⚠️ 题目要求"递减有序"，所以要用头插法。如果要求"递增有序"，就要用尾插法。一定要看清题目要求！

2.2 命题规律总结

根据近10年（2014-2023）408真题统计，线性表部分的命题规律如下：

趋势分析：

1. 出题频率： 线性表部分每年必考，通常是1道选择题（2分）+ 1道算法题（15分），共17分。
2. 难度趋势： 选择题难度稳定在L1-L2，算法题难度稳定在L3。整体难度保持稳定，没有明显上升或下降。
3. 题型偏好：
   • 选择题： 偏重概念辨析和代码判断，常考头结点、循环链表、时间复杂度
   • 算法题： 偏重双指针法、有序合并、原地逆置，要求写出完整代码并分析复杂度
4. 常见陷阱：
   • 选择题：混淆"带头结点"和"不带头结点"、混淆"循环链表"和"普通链表"
   • 算法题：忽略边界条件、指针操作顺序错误、复杂度分析不准确

备考建议：

1. 选择题备考：
   • 熟练掌握头结点、循环链表的基本概念
   • 熟练掌握各种操作的时间复杂度
   • 多做"代码判断"类题目，提高指针操作的敏感度
2. 算法题备考：
   • 熟练掌握双指针法、头插法、尾插法
   • 熟练掌握有序合并、原地逆置的经典代码
   • 写完代码后一定要检查边界条件
   • 一定要写复杂度分析，这是评分标准的一部分

模块3：AI命题Prompt ≈ 5000 字

3.1 命题Prompt模板

【AI命题Prompt - 可复制使用】

请你扮演一位考研408数据结构辅导专家，根据以下要求命制一套练习题：

📌 章节范围：第1章 线性表
📌 知识点范围：顺序表与链表选型、插入删除时间复杂度、头结点的作用、循环链表判空条件、双指针法应用、有序合并、原地逆置、指针操作陷阱、边界条件处理、复杂度分析

📋 题目要求：
- 题目数量：共 12 道
- 题型分布：选择题 6 道、算法题 2 道、简答题 4 道
- 难度分布：L1基础 3 道、L2应用 5 道、L3综合 4 道

📋 输出格式要求：
1. 每道题先给出题目
2. 然后给出【参考答案】和【解题思路】
3. 标注每道题考察的知识点
4. 最后给出整体难度评估

请确保题目贴近真题风格，难度与真题相当。选择题要包含"代码判断"类题目，算法题要包含"双指针法"和"有序合并"，简答题要包含"概念辨析"和"复杂度分析"。

3.2 AI生成的题目示例

以下是使用上述Prompt生成的题目示例：

选择题1（L1基础）

题目： 线性表最常用的两种存储结构是顺序表和链表，下列关于顺序表和链表的说法中，正确的是（）

A. 顺序表的存储密度小于链表 B. 顺序表的按位查找时间复杂度为O(n) C. 链表的插入删除时间复杂度为O(1)（已知位置） D. 链表适合频繁访问的场景

参考答案： C

解题思路：

• A错误：顺序表的存储密度等于1，链表的存储密度小于1
• B错误：顺序表的按位查找时间复杂度为O(1)
• C正确：链表在已知位置的情况下，插入删除只需要修改指针，时间复杂度为O(1)
• D错误：链表适合频繁插入删除的场景，不适合频繁访问

考察知识点： 顺序表与链表对比、存储密度、时间复杂度

选择题2（L2应用）

题目： 设某单链表带有头结点，头指针为head，则判断单链表为满的条件是（）

A. head == NULL B. head->next == NULL C. 不存在"为满"的条件 D. head->next == head

参考答案： C

解题思路：

• 单链表采用动态分配，不需要预先分配固定大小的空间
• 因此单链表不存在"为满"的条件
• 只有顺序表（静态分配）才有"为满"的条件：length == maxSize

考察知识点： 单链表、动态分配、判满条件

选择题3（L2应用）

题目： 设指针p指向单链表中的某个结点，该结点的后继结点为q，若要删除q，则需要修改的指针是（）

A. p->next B. q->next C. p D. q

参考答案： A

解题思路：

• 要删除q（p的后继结点）
• 需要让p的next指向q的后继结点
• 即修改p->next：p->next = q->next
• 然后释放q的空间：free(q)

考察知识点： 单链表删除、指针修改

选择题4（L2应用）

题目： 下列关于循环双链表的说法中，错误的是（）

A. 循环双链表中没有NULL指针 B. 循环双链表的判空条件是head->next == head && head->prior == head C. 循环双链表可以从任意结点出发遍历整个链表 D. 循环双链表的插入操作只需要修改一个指针

参考答案： D

解题思路：

• A正确：循环双链表的最后一个结点的next指向头结点，头结点的prior指向尾结点，没有NULL指针
• B正确：空表时，头结点的next和prior都指向自己
• C正确：循环双链表是双向循环的，可以从任意结点出发向任意方向遍历
• D错误：循环双链表的插入操作需要修改4个指针（新结点的prior和next，前驱的next，后继的prior）

考察知识点： 循环双链表、判空条件、插入操作

选择题5（L3综合）

题目： 设某算法对单链表进行如下操作：从头到尾遍历链表，对于每个结点，将其next指针指向其前驱结点。则该算法实现的功能是（）

A. 删除链表 B. 逆置链表 C. 合并链表 D. 拆分链表

参考答案： B

解题思路：

• 遍历链表，将每个结点的next指针指向其前驱
• 这等价于将所有结点的指针方向反转
• 即实现了链表的逆置
• 这是"三指针法"逆置链表的核心思想

考察知识点： 链表逆置、三指针法、指针操作

选择题6（L3综合）

题目： 设某单链表带有头结点，头指针为head，尾指针为rear，则该链表为循环单链表的条件是（）

A. rear->next == head B. rear->next == NULL C. rear == head D. rear->next == rear

参考答案： A

解题思路：

• 循环单链表的最后一个结点的next指向头结点
• rear指向尾结点，所以rear->next应该指向头结点head
• 即rear->next == head

考察知识点： 循环单链表、尾指针、结构特点

算法题1（L3综合）

题目： 设计一个算法，找出单链表的中间结点。如果链表长度为偶数，返回中间两个结点中的第一个。要求时间复杂度为O(n)，空间复杂度为O(1)。

参考答案：

LNode* findMiddle(LNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;  // 空表或只有一个结点
    }
    
    LNode *slow = head, *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;        // 慢指针走1步
        fast = fast->next->next;  // 快指针走2步
    }
    
    return slow;  // 慢指针指向的就是中间结点
}

解题思路：

• 使用快慢指针法
• 快指针每次走2步，慢指针每次走1步
• 当快指针到达末尾时，慢指针正好在中间
• 如果链表长度为偶数，快指针会停在倒数第二个结点，慢指针指向中间两个结点中的第一个

时间复杂度： O(n) 空间复杂度： O(1)

考察知识点： 双指针法、快慢指针、中间结点

算法题2（L3综合）

题目： 设计一个算法，判断单链表是否为回文结构。要求时间复杂度为O(n)，空间复杂度为O(1)。

参考答案：

bool isPalindrome(LNode *head) {
    if (head == NULL || head->next == NULL) {
        return true;  // 空表或只有一个结点，是回文
    }
    
    // 第一步：找到中间结点
    LNode *slow = head, *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 第二步：逆置后半部分
    LNode *secondHalf = slow->next;
    slow->next = NULL;  // 断开前后两部分
    
    // 逆置后半部分
    LNode *prev = NULL, *curr = secondHalf;
    while (curr != NULL) {
        LNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    secondHalf = prev;  // secondHalf指向逆置后的头
    
    // 第三步：比较前后两部分
    LNode *p1 = head, *p2 = secondHalf;
    bool result = true;
    while (p2 != NULL) {  // 只需要比较后半部分的长度
        if (p1->data != p2->data) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    // 第四步：恢复链表（可选）
    // 重新逆置后半部分
    prev = NULL;
    curr = secondHalf;
    while (curr != NULL) {
        LNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    slow->next = prev;
    
    return result;
}

解题思路：

• 第一步：用快慢指针找到中间结点
• 第二步：逆置后半部分
• 第三步：比较前后两部分是否相同
• 第四步：恢复链表（可选，但推荐）

时间复杂度： O(n) 空间复杂度： O(1)

考察知识点： 双指针法、链表逆置、回文判断

简答题1（L2应用）

题目： 简述头结点的作用。

参考答案：

头结点有三个主要作用：

1. 统一空表和非空表的处理
   • 有头结点：空表判断条件是head->next == NULL
   • 无头结点：空表判断条件是head == NULL
   • 有头结点可以统一处理逻辑，简化代码
2. 统一插入删除操作
   • 有头结点：在第一个位置插入/删除时，操作方式与其他位置相同
   • 无头结点：在第一个位置插入/删除时，需要特殊处理（修改头指针）
3. 方便遍历
   • 有头结点：遍历从head->next开始，逻辑统一
   • 无头结点：遍历从head开始，需要特殊处理第一个结点

考察知识点： 头结点、代码简化、统一处理

简答题2（L2应用）

题目： 比较顺序表和链表的优缺点。

参考答案：

顺序表的优点：

• 支持随机访问，按位查找时间复杂度O(1)
• 存储密度高，不需要额外的指针空间
• 缓存友好，连续内存访问效率高

顺序表的缺点：

• 插入删除需要移动大量元素
• 需要预先分配固定大小的空间，可能造成浪费或溢出

链表的优点：

• 插入删除不需要移动元素，只需修改指针
• 动态分配，不需要预先分配固定大小的空间

链表的缺点：

• 不支持随机访问，按位查找时间复杂度O(n)
• 需要额外的指针空间，存储密度低
• 缓存不友好，离散内存访问效率低

考察知识点： 顺序表与链表对比、优缺点、适用场景

简答题3（L3综合）

题目： 简述双指针法的原理和应用场景。

参考答案：

双指针法的原理：

• 使用两个指针在链表上移动，通过两个指针的相对位置或移动速度来解决问题
• 常见的双指针法有：快慢指针、前后指针、对撞指针

快慢指针：

• 快指针每次走2步，慢指针每次走1步
• 应用场景：找中间结点、检测环、找环的入口、找倒数第k个结点

前后指针：

• 两个指针保持固定的距离
• 应用场景：找倒数第k个结点

对撞指针：

• 两个指针从两端向中间移动
• 应用场景：判断回文、两数之和

考察知识点： 双指针法、快慢指针、应用场景

简答题4（L3综合）

题目： 分析顺序表插入操作的时间复杂度。

参考答案：

设顺序表长度为n，在第i个位置插入元素（1 ≤ i ≤ n+1）。

最好情况： i = n+1（在表尾插入），不需要移动元素，时间复杂度O(1)

最坏情况： i = 1（在表头插入），需要移动n个元素，时间复杂度O(n)

平均情况： 假设在任意位置插入的概率相等，即p_i = 1/(n+1)

所以平均时间复杂度为O(n)。

考察知识点： 时间复杂度、平均情况分析、数学推导

3.3 使用说明

如何使用这个Prompt：

1. 复制Prompt： 将上面的Prompt模板复制到AI工具中
2. 调整参数： 根据需要调整题目数量、题型分布、难度分布
3. 生成题目： 让AI生成题目
4. 验证质量： 检查生成的题目是否贴近真题风格，难度是否合适
5. 做答并批改： 限时完成题目，然后对照答案批改

注意事项：

• AI生成的题目可能与真题有差异，需要人工审核
• 如果题目太难或太简单，可以调整难度分布参数
• 建议每次生成12-15道题目，覆盖所有核心考点
• 做完题目后，一定要分析错题，找出知识漏洞

推荐使用的AI工具：

• ChatGPT：生成质量较高，理解能力强
• Claude：生成质量高，逻辑清晰
• 文心一言：中文理解能力强，适合生成中文题目

模块4：AI讲题Prompt ≈ 5000 字

4.1 讲题Prompt模板

【AI讲题Prompt - 可复制使用】

请你扮演一位考研408数据结构辅导老师，对以下易错题进行详细讲解：

📌 题目：
（在此粘贴需要讲解的题目）

📋 讲解要求：
1. 第一步：分析题目考察的知识点
2. 第二步：指出解题的关键突破口
3. 第三步：逐步推导，每一步都说明"为什么这样做"
4. 第四步：总结此类题的通用解法
5. 第五步：给出2道变式题（难度相近但考法不同）

📋 特别注意：
- 不要直接给答案，采用引导式提问
- 指出常见的错误思路及为什么错
- 用通俗语言解释抽象概念
- 画图辅助说明（如果适用）

4.2 AI生成的讲解示例

示例1：双指针法找倒数第k个结点

题目： 设计一个算法，找出单链表中倒数第k个结点。如果不存在，返回NULL。

知识点分析：

• 本题考察的核心知识点是"双指针法"
• 双指针法是线性表算法题的高频考点
• 常见的双指针法应用：找倒数第k个结点、找中间结点、检测环

解题突破口：

• 突破口在于"倒数第k个"这个关键词
• 看到"倒数第k个"，就应该想到双指针法
• 双指针法的核心思想：让第一个指针先走k步，然后两个指针一起走，当第一个指针到达末尾时，第二个指针就是倒数第k个

逐步推导：

问题1：为什么要用双指针法？

• 方法一：先遍历一遍求出长度n，再遍历一遍找第n-k+1个结点
  • 时间复杂度：O(2n) = O(n)
  • 缺点：需要遍历两次
• 方法二：双指针法
  • 时间复杂度：O(n)
  • 优点：只需要遍历一次
• 结论：双指针法更优

问题2：双指针法的具体实现是什么？

• 让第一个指针p先走k步
• 然后p和q一起走，每次走1步
• 当p到达末尾（p == NULL）时，q就是倒数第k个

问题3：如何判断k > n的情况？

• 如果p走了k步后，q还没有开始走，说明k > n
• 可以用一个计数器count记录p走了多少步
• 最后检查count < k，如果是，则返回NULL

问题4：边界条件有哪些？

• k <= 0：返回NULL
• k > n：返回NULL
• 空表：返回NULL

完整代码：

LNode* findKthFromEnd(LNode *head, int k) {
    if (k <= 0 || head == NULL) {
        return NULL;  // 边界条件
    }
    
    LNode *p = head, *q = head;
    int count = 0;
    
    // 第一个指针先走k步
    while (p != NULL) {
        p = p->next;
        count++;
        if (count > k) {  // 当第一个指针走了k步后，第二个指针开始走
            q = q->next;
        }
    }
    
    // 如果链表长度小于k，返回NULL
    if (count < k) {
        return NULL;
    }
    
    return q;
}

通用解法总结：

双指针法的通用模板：

// 找倒数第k个结点
LNode *p = head, *q = head;
int count = 0;
while (p != NULL) {
    p = p->next;
    count++;
    if (count > k) {
        q = q->next;
    }
}
if (count < k) return NULL;
return q;

双指针法的其他应用：

1. 找中间结点：

LNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}
return slow;

1. 检测环：

LNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;  // 有环
}
return false;  // 无环

变式题1： 设计一个算法，找出单链表的中间结点。如果链表长度为偶数，返回中间两个结点中的第一个。

参考答案：

LNode* findMiddle(LNode *head) {
    LNode *slow = head, *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

变式题2： 设计一个算法，判断单链表是否有环。如果有环，返回环的入口结点；如果没有环，返回NULL。

参考答案：

LNode* detectCycle(LNode *head) {
    LNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {  // 有环
            slow = head;  // 慢指针重新指向头
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;  // 相遇点就是环的入口
        }
    }
    return NULL;  // 无环
}

示例2：有序合并

题目： 设计一个算法，将两个递增有序的单链表合并为一个递增有序的单链表。要求在原链表的基础上进行合并，不申请新结点。

知识点分析：

• 本题考察的核心知识点是"有序合并"
• 有序合并是线性表算法题的高频考点
• 常见的有序合并：递增合并为递增、递增合并为递减

解题突破口：

• 突破口在于"递增有序"和"不申请新结点"
• 由于两个链表都是递增有序的，可以依次比较两个链表的当前最小元素
• 由于要求合并后仍为递增有序，可以使用尾插法
• 由于要求不申请新结点，需要在原链表的基础上进行合并

逐步推导：

问题1：为什么要用尾插法？

• 如果要求合并后为递增有序，应该用尾插法
• 如果要求合并后为递减有序，应该用头插法
• 本题要求递增有序，所以用尾插法

问题2：如何在不申请新结点的情况下合并？

• 依次比较两个链表的当前最小元素
• 将较小的元素从原链表中"摘下"
• 用尾插法插入结果链表
• 结果链表可以复用其中一个链表的头结点

问题3：如何处理剩余部分？

• 当其中一个链表遍历完毕后，另一个链表的剩余部分直接接在结果链表末尾

完整代码：

LNode* mergeSortedLists(LNode *A, LNode *B) {
    // A和B分别是两个递增有序链表的头指针
    LNode *C = A;  // 复用A的头结点作为结果链表的头结点
    LNode *pa = A->next, *pb = B->next;
    LNode *rc = C;  // rc是结果链表的尾指针
    
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            rc->next = pa;
            rc = pa;
            pa = pa->next;
        } else {
            rc->next = pb;
            rc = pb;
            pb = pb->next;
        }
    }
    
    // 处理剩余部分
    if (pa != NULL) {
        rc->next = pa;
    } else {
        rc->next = pb;
    }
    
    // 释放B的头结点
    free(B);
    
    return C;
}

通用解法总结：

有序合并的通用模板（递增合并为递增）：

LNode* mergeSortedLists(LNode *A, LNode *B) {
    LNode *C = A;
    LNode *pa = A->next, *pb = B->next;
    LNode *rc = C;
    
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            rc->next = pa;
            rc = pa;
            pa = pa->next;
        } else {
            rc->next = pb;
            rc = pb;
            pb = pb->next;
        }
    }
    
    rc->next = (pa != NULL) ? pa : pb;
    free(B);
    return C;
}

有序合并的其他变体：

1. 递增合并为递减： 使用头插法
2. 递减合并为递增： 先逆置，再合并
3. 递减合并为递减： 使用头插法

变式题1： 设计一个算法，将两个递增有序的单链表合并为一个递减有序的单链表。要求在原链表的基础上进行合并，不申请新结点。

参考答案：

LNode* mergeAndReverse(LNode *A, LNode *B) {
    LNode *C = NULL;
    LNode *pa = A, *pb = B;
    
    while (pa != NULL && pb != NULL) {
        LNode *s;
        if (pa->data <= pb->data) {
            s = pa;
            pa = pa->next;
        } else {
            s = pb;
            pb = pb->next;
        }
        s->next = C;
        C = s;
    }
    
    LNode *r = (pa != NULL) ? pa : pb;
    while (r != NULL) {
        LNode *s = r;
        r = r->next;
        s->next = C;
        C = s;
    }
    
    return C;
}

变式题2： 设计一个算法，将两个递减有序的单链表合并为一个递增有序的单链表。

参考答案：

LNode* mergeDecreasingToIncreasing(LNode *A, LNode *B) {
    // 先逆置A和B，使其变为递增有序
    A = reverseList(A);
    B = reverseList(B);
    // 再合并为递增有序
    return mergeSortedLists(A, B);
}

4.3 易错题记录

根据学生反馈，线性表部分最容易出错的题目有：

1. 双指针法找倒数第k个结点
   • 共同特点：容易忽略边界条件（k <= 0、k > n）
   • 解题关键：熟练掌握双指针法的模板
2. 有序合并
   • 共同特点：容易混淆"尾插法"和"头插法"
   • 解题关键：看清题目要求（递增还是递减）
3. 原地逆置
   • 共同特点：容易丢失后继结点的地址
   • 解题关键：先保存后继，再修改指针
4. 循环链表判空
   • 共同特点：容易混淆"普通链表"和"循环链表"的判空条件
   • 解题关键：记住"循环链表无NULL"

模块5：AI错题复盘Prompt ≈ 5000 字

5.1 错题复盘Prompt模板

【AI错题复盘Prompt - 可复制使用】

请你扮演一位考研408数据结构辅导专家，帮我分析以下错题：

📌 我的错题：
（在此粘贴做错的题目）

📌 我的错误解答：
（在此写下你的错误解题过程）

📌 正确答案：
（粘贴正确答案）

📋 分析要求：
1. 【错因诊断】分析我出错的根本原因：
   - 是概念理解错误？计算失误？还是方法选择不当？
   - 具体是哪个知识点存在漏洞？

2. 【知识漏洞定位】指出我需要回看的教材章节/知识点

3. 【正确思路】给出正确的解题思路与关键步骤

4. 【强化训练】针对我的薄弱环节，出3道同类型练习题
   - 第1道：基础巩固（L1-L2）
   - 第2道：中等难度（L3）
   - 第3道：综合提升（L3-L4）

5. 【防错提醒】总结一句"下次遇到类似题一定要注意..."的提醒

5.2 AI生成的复盘示例

示例1：循环链表判空条件错误

我的错题： 设循环单链表head为空的判断条件是（） A. head->next == NULL B. head->next == head C. head == NULL D. head->prior == head

我的错误解答： 选A

正确答案： B

错因诊断：

• 根本原因： 概念理解错误
• 具体漏洞： 混淆了"普通单链表"和"循环单链表"的判空条件
• 错误分析：
  • 普通单链表的判空条件是head->next == NULL（有头结点）或head == NULL（无头结点）
  • 循环单链表的判空条件是head->next == head
  • 循环链表的特点是最后一个结点的next指向头结点，而不是NULL
  • 所以空表时，头结点的next指向自己，而不是NULL

知识漏洞定位：

• 需要回看：DS-01-04 双链表、循环链表与静态链表
• 重点复习：循环链表的结构特点、判空条件

正确思路：

1. 识别题目关键词：“循环单链表”
2. 回忆循环链表的特点：没有NULL指针，最后一个结点的next指向头结点
3. 空表时，头结点的next指向自己
4. 所以判空条件是head->next == head

强化训练：

第1道（基础巩固）： 设某单链表带有头结点，头指针为head，则判断单链表为空的条件是（） A. head == NULL B. head->next == NULL C. head->next == head D. head != NULL

参考答案： B

第2道（中等难度）： 设某循环双链表带有头结点，头指针为head，则判断循环双链表为空的条件是（） A. head->next == NULL B. head->next == head C. head->next == head && head->prior == head D. head->prior == head

参考答案： C

第3道（综合提升）： 设某循环单链表带有头结点和尾指针，头指针为head，尾指针为rear，则判断循环单链表为空的条件是（） A. rear == head B. rear->next == head C. head->next == rear D. rear->next == rear

参考答案： A（空表时，尾指针指向头结点）

防错提醒： 下次遇到"循环链表"的题目，一定要注意"循环链表无NULL"这个特点。判空条件一定是"指向自己"，而不是"指向NULL"。

示例2：双指针法边界条件遗漏

我的错题： 设计一个算法，找出单链表中倒数第k个结点。

我的错误解答：

LNode* findKthFromEnd(LNode *head, int k) {
    int n = 0;
    LNode *p = head->next;
    while (p) {
        n++;
        p = p->next;
    }
    p = head->next;
    for (int i = 0; i < n - k; i++) {
        p = p->next;
    }
    return p;
}

正确答案：

LNode* findKthFromEnd(LNode *head, int k) {
    if (k <= 0 || head == NULL) {
        return NULL;
    }
    
    LNode *p = head, *q = head;
    int count = 0;
    
    while (p != NULL) {
        p = p->next;
        count++;
        if (count > k) {
            q = q->next;
        }
    }
    
    if (count < k) {
        return NULL;
    }
    
    return q;
}

错因诊断：

• 根本原因： 方法选择不当 + 边界条件遗漏
• 具体漏洞：
  1. 方法选择不当：使用了"先求长度再找"的方法，时间复杂度O(2n)，不如双指针法O(n)
  2. 边界条件遗漏：没有处理k <= 0和k > n的情况
• 错误分析：
  • 当k > n时，n - k是负数，for循环不会执行，直接返回p，但p指向的是首元结点，而不是倒数第k个
  • 当k <= 0时，n - k会变大，导致访问越界

知识漏洞定位：

• 需要回看：DS-01-06 线性表的算法题解题方法
• 重点复习：双指针法、边界条件处理

正确思路：

1. 识别题目关键词：“倒数第k个”
2. 想到双指针法
3. 处理边界条件：k <= 0、k > n、空表
4. 实现双指针法

强化训练：

第1道（基础巩固）： 设计一个算法，找出单链表的中间结点。

参考答案：

LNode* findMiddle(LNode *head) {
    LNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

第2道（中等难度）： 设计一个算法，判断单链表是否有环。

参考答案：

bool hasCycle(LNode *head) {
    LNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

第3道（综合提升）： 设计一个算法，判断单链表是否有环。如果有环，返回环的入口结点；如果没有环，返回NULL。

参考答案：

LNode* detectCycle(LNode *head) {
    LNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}

防错提醒： 下次遇到"倒数第k个"、“中间结点”、"环的检测"等题目，一定要想到双指针法。写完代码后，一定要检查边界条件：k <= 0、k > n、空表。

5.3 错题归因统计

根据学生反馈，线性表部分错题的原因分类如下：

主要薄弱环节：

1. 概念混淆：头结点、循环链表的基本概念不清晰
2. 边界条件遗漏：算法题中容易忽略特殊情况
3. 指针操作错误：指针修改顺序错误，导致指针丢失

针对性改进建议：

1. 概念混淆： 制作对比表格，系统梳理头结点、循环链表的基本概念
2. 边界条件遗漏： 建立"边界条件检查清单"，每次写完代码后逐项检查
3. 指针操作错误： 多做"代码判断"类题目，提高指针操作的敏感度

模块6：AI模拟卷Prompt ≈ 8000 字

6.1 模拟卷Prompt模板

【AI模拟卷Prompt - 可复制使用】

请你扮演一位考研408数据结构命题组专家，根据以下要求生成一套章节模拟卷：

📌 章节范围：第1章 线性表
📌 知识点范围：顺序表与链表选型、插入删除时间复杂度、头结点的作用、循环链表判空条件、双指针法应用、有序合并、原地逆置、指针操作陷阱、边界条件处理、复杂度分析

📋 试卷结构：
- 选择题：5 道，每题 4 分，共 20 分
- 填空题：5 道，每题 4 分，共 20 分
- 解答题：5 道，共 60 分
- 总分：100 分
- 建议用时：120 分钟

📋 难度分布：
- 基础题（L1-L2）：占 40%
- 中等题（L3）：占 40%
- 较难题（L4-L5）：占 20%

📋 输出要求：
1. 先输出完整试卷（不含答案）
2. 然后输出参考答案与评分标准
3. 每道解答题标注"踩分点"
4. 最后给出分数段评估建议：
   - 90分以上：掌握良好，可以继续下一章
   - 75-89分：部分薄弱，建议重点复习...
   - 60-74分：基本掌握，建议系统复习本章
   - 60分以下：基础不牢，建议重新学习本章

6.2 AI生成的完整模拟卷

第1章 线性表 模拟卷

总分：100分 建议用时：120分钟

一、选择题（每题4分，共20分）

1. 对于一个经常进行访问操作的线性表，为提高操作效率，应采用的存储结构是（） A. 顺序表 B. 单链表 C. 双链表 D. 循环链表
2. 设某单链表带有头结点，头指针为head，则判断单链表为非空的条件是（） A. head == NULL B. head->next == NULL C. head->next != NULL D. head != NULL
3. 设指针p指向单链表中的某个结点，若要删除p的后继结点，则需要修改的指针是（） A. p->next B. p->next->next C. p D. p->next->next->next
4. 设某循环单链表带有头结点，头指针为head，则判断循环单链表为空的条件是（） A. head == NULL B. head->next == NULL C. head->next == head D. head->next != head
5. 设某算法对单链表进行如下操作：使用两个指针p和q，p每次走2步，q每次走1步，当p到达末尾时，q指向的结点是（） A. 第一个结点 B. 最后一个结点 C. 中间结点 D. 头结点

二、填空题（每题4分，共20分）

1. 顺序表的按位查找时间复杂度为______，链表的按位查找时间复杂度为______。
2. 在单链表中，若要在指针p所指结点之后插入新结点s，则需要执行的操作是______和______。
3. 在双链表中，若要在指针p所指结点之后插入新结点s，则需要修改______个指针。
4. 循环双链表的判空条件是______。
5. 双指针法找倒数第k个结点的时间复杂度为______，空间复杂度为______。

三、解答题（共60分）

1. （10分）简述头结点的三个作用。
2. （10分）比较顺序表和链表的优缺点，并说明各自的适用场景。
3. （12分）设计一个算法，将单链表原地逆置。要求空间复杂度为O(1)。
4. （14分）设计一个算法，找出单链表中倒数第k个结点。如果不存在，返回NULL。要求时间复杂度为O(n)。
5. （14分）设计一个算法，将两个递增有序的单链表合并为一个递增有序的单链表。要求在原链表的基础上进行合并，不申请新结点。

参考答案与评分标准

一、选择题（每题4分，共20分）

1. 答案： A 解析： 顺序表支持随机访问，按位查找时间复杂度O(1)，适合频繁访问的场景。
2. 答案： C 解析： 有头结点的单链表，非空的条件是头结点的指针域不为空，即head->next != NULL。
3. 答案： A 解析： 删除p的后继结点，需要修改p->next，使其指向后继的后继。
4. 答案： C 解析： 循环单链表空表时，头结点的next指向自己，即head->next == head。
5. 答案： C 解析： 快慢指针法，快指针每次走2步，慢指针每次走1步，当快指针到达末尾时，慢指针指向中间结点。

二、填空题（每题4分，共20分）

1. 答案： O(1)，O(n) 评分标准： 每空2分
2. 答案： s->next = p->next，p->next = s 评分标准： 每空2分，顺序不能颠倒
3. 答案： 4 评分标准： 4分
4. 答案： head->next == head && head->prior == head 评分标准： 4分
5. 答案： O(n)，O(1) 评分标准： 每空2分

三、解答题（共60分）

1. （10分）简述头结点的三个作用。

参考答案： 头结点有三个主要作用：

1. 统一空表和非空表的处理（3分）
   • 有头结点：空表判断条件是head->next == NULL
   • 无头结点：空表判断条件是head == NULL
   • 有头结点可以统一处理逻辑，简化代码
2. 统一插入删除操作（3分）
   • 有头结点：在第一个位置插入/删除时，操作方式与其他位置相同
   • 无头结点：在第一个位置插入/删除时，需要特殊处理（修改头指针）
3. 方便遍历（3分）
   • 有头结点：遍历从head->next开始，逻辑统一
   • 无头结点：遍历从head开始，需要特殊处理第一个结点

表述清晰、逻辑完整（1分）

2. （10分）比较顺序表和链表的优缺点，并说明各自的适用场景。

参考答案：

顺序表的优点：（2分）

• 支持随机访问，按位查找时间复杂度O(1)
• 存储密度高，不需要额外的指针空间

顺序表的缺点：（2分）

• 插入删除需要移动大量元素
• 需要预先分配固定大小的空间

链表的优点：（2分）

• 插入删除不需要移动元素，只需修改指针
• 动态分配，不需要预先分配固定大小的空间

链表的缺点：（2分）

• 不支持随机访问，按位查找时间复杂度O(n)
• 需要额外的指针空间，存储密度低

适用场景：（2分）

• 顺序表：频繁访问、少量插入删除
• 链表：频繁插入删除、少量访问

3. （12分）设计一个算法，将单链表原地逆置。要求空间复杂度为O(1)。

参考答案：

LNode* reverseList(LNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;  // 空表或只有一个结点，无需逆置
    }
    
    LNode *p = head->next;  // p指向首元结点
    LNode *r;               // r用于保存p的后继
    head->next = NULL;      // 头结点的next置为NULL
    
    while (p != NULL) {
        r = p->next;        // 保存p的后继
        p->next = head->next;  // p的next指向首元结点
        head->next = p;     // 头结点的next指向p
        p = r;              // p指向下一个结点
    }
    
    return head;
}

评分标准：

• 算法思路正确（头插法）：4分
• 代码实现正确：6分
  • 边界条件处理：1分
  • 指针操作正确：4分
  • 代码规范：1分
• 复杂度分析正确：2分
  • 时间复杂度O(n)：1分
  • 空间复杂度O(1)：1分

4. （14分）设计一个算法，找出单链表中倒数第k个结点。如果不存在，返回NULL。要求时间复杂度为O(n)。

参考答案：

LNode* findKthFromEnd(LNode *head, int k) {
    if (k <= 0 || head == NULL) {
        return NULL;  // 边界条件
    }
    
    LNode *p = head, *q = head;
    int count = 0;
    
    // 第一个指针先走k步
    while (p != NULL) {
        p = p->next;
        count++;
        if (count > k) {  // 当第一个指针走了k步后，第二个指针开始走
            q = q->next;
        }
    }
    
    // 如果链表长度小于k，返回NULL
    if (count < k) {
        return NULL;
    }
    
    return q;
}

评分标准：

• 算法思路正确（双指针法）：4分
• 代码实现正确：8分
  • 边界条件处理（k <= 0、k > n）：2分
  • 双指针法实现：5分
  • 代码规范：1分
• 复杂度分析正确：2分
  • 时间复杂度O(n)：1分
  • 空间复杂度O(1)：1分

5. （14分）设计一个算法，将两个递增有序的单链表合并为一个递增有序的单链表。要求在原链表的基础上进行合并，不申请新结点。

参考答案：

LNode* mergeSortedLists(LNode *A, LNode *B) {
    // A和B分别是两个递增有序链表的头指针
    LNode *C = A;  // 复用A的头结点作为结果链表的头结点
    LNode *pa = A->next, *pb = B->next;
    LNode *rc = C;  // rc是结果链表的尾指针
    
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            rc->next = pa;
            rc = pa;
            pa = pa->next;
        } else {
            rc->next = pb;
            rc = pb;
            pb = pb->next;
        }
    }
    
    // 处理剩余部分
    if (pa != NULL) {
        rc->next = pa;
    } else {
        rc->next = pb;
    }
    
    // 释放B的头结点
    free(B);
    
    return C;
}

评分标准：

• 算法思路正确（归并思想+尾插法）：4分
• 代码实现正确：8分
  • 归并思想实现：4分
  • 尾插法实现：3分
  • 代码规范：1分
• 复杂度分析正确：2分
  • 时间复杂度O(m+n)：1分
  • 空间复杂度O(1)：1分

6.3 评分标准参考

分数段评估建议：

• 90分以上： 掌握良好，可以继续下一章
  • 说明你对线性表的基本概念、操作、算法都掌握得很好
  • 建议：可以适当做一些综合题，提高解题速度
• 75-89分： 部分薄弱，建议重点复习…
  • 说明你掌握了大部分知识点，但还有一些薄弱环节
  • 建议：分析错题，找出知识漏洞，有针对性地强化
• 60-74分： 基本掌握，建议系统复习本章
  • 说明你掌握了基本概念，但操作和算法还不够熟练
  • 建议：重新学习DS-01-01到DS-01-06，重点练习代码实现
• 60分以下： 基础不牢，建议重新学习本章
  • 说明你对线性表的基本概念还不清晰
  • 建议：从DS-01-01开始重新学习，每篇文章都要认真做笔记和练习

模块7：延伸阅读 ≈ 3000 字

7.1 教材参考

1. 《数据结构（C语言版）》——严蔚敏、吴伟民

• 推荐章节： 第2章 线性表（P20-P60）
• 阅读重点：
  • 2.1 线性表的定义和基本操作（P20-P25）
  • 2.2 顺序表（P25-P35）
  • 2.3 链表（P35-P55）
• 特点： 经典教材，理论扎实，代码规范，适合打基础
• 适用人群： 初学者、基础薄弱的同学

2. 《数据结构复习指导》——王道考研

• 推荐章节： 第2章 线性表（P1-P80）
• 阅读重点：
  • 2.1 线性表的基本概念（P1-P10）
  • 2.2 顺序表和链表（P10-P40）
  • 2.3 线性表的应用（P40-P60）
  • 2.4 真题精选（P60-P80）
• 特点： 针对408考试，知识点总结精炼，真题解析详细
• 适用人群： 备考408的同学

3. 《数据结构与算法分析——C语言描述》——Mark Allen Weiss

• 推荐章节： 第3章 表、栈和队列（P50-P100）
• 阅读重点：
  • 3.1 抽象数据类型（ADT）（P50-P55）
  • 3.2 表ADT（P55-P60）
  • 3.3 链表（P60-P80）
  • 3.4 顺序表（P80-P90）
• 特点： 国外经典教材，注重算法分析，代码优雅
• 适用人群： 想深入学习算法分析的同学

7.2 视频课程

1. 【B站】王道考研数据结构

• 链接： https://www.bilibili.com/video/BV1b7411N798
• 推荐章节： 第2章 线性表（P1-P20）
• 讲师特点： 讲解清晰，重点突出，真题解析详细
• 适合人群： 备考408的同学
• 观看建议： 先看视频理解概念，再做真题巩固

2. 【B站】青岛大学数据结构

• 链接： https://www.bilibili.com/video/BV1nJ411V7vC
• 推荐章节： 第2章 线性表（P1-P15）
• 讲师特点： 讲解细致，代码演示清晰，适合初学者
• 适合人群： 基础薄弱、初学数据结构的同学
• 观看建议： 配合教材一起学习，效果更好

3. 【B站】小甲鱼数据结构

• 链接： https://www.bilibili.com/video/BV1jx411N7AN
• 推荐章节： 第2章 线性表（P1-P12）
• 讲师特点： 幽默风趣，通俗易懂，代码实现详细
• 适合人群： 喜欢轻松学习氛围的同学
• 观看建议： 适合入门，但深度不够，需要配合其他资料

4. 【中国大学MOOC】数据结构——浙江大学

• 链接： https://www.icourse163.org/course/ZJU-93001
• 推荐章节： 第2章 线性结构（P1-P10）
• 讲师特点： 理论扎实，讲解深入，适合系统学习
• 适合人群： 想系统学习数据结构的同学
• 观看建议： 课程较长，需要有耐心

7.3 知识关联图

前置知识：

• C语言基础：指针、结构体、动态内存分配
• 算法基础：时间复杂度、空间复杂度分析

后续知识：

• 第2章 栈、队列和数组：栈和队列是特殊的线性表
• 第3章 树与二叉树：树的存储结构用到了链表
• 第4章 图：图的存储结构用到了邻接表（链表的应用）

学习路径建议：

1. 先掌握C语言基础，特别是指针和结构体
2. 系统学习线性表的基本概念和操作
3. 多做真题，熟练掌握线性表的应用
4. 学习栈、队列时，注意与线性表的联系
5. 学习树、图时，注意链表的应用

模块8：本章Checklist ≈ 2500 字

8.1 知识点清单

基本概念（L1）

• 能说出线性表的定义和逻辑特征
• 能区分顺序表和链表的存储结构
• 能说出头结点的三个作用
• 能区分"带头结点"和"不带头结点"的判空条件
• 能区分"普通链表"和"循环链表"的判空条件

顺序表（L2）

• 能写出顺序表的静态分配和动态分配代码
• 能写出顺序表的插入、删除、查找代码
• 能分析顺序表插入、删除的时间复杂度（最好、最坏、平均）
• 能说出顺序表的优缺点和适用场景

链表（L2）

• 能写出单链表的结点定义和初始化代码
• 能写出单链表的插入、删除、查找代码
• 能写出双链表的结点定义和插入、删除代码
• 能写出循环链表的判空条件
• 能说出链表的优缺点和适用场景

应用（L3）

• 能用双指针法找倒数第k个结点
• 能用双指针法找中间结点
• 能用双指针法检测环
• 能写出有序合并的代码（递增合并为递增/递减）
• 能写出原地逆置的代码（头插法/三指针法）
• 能处理算法题中的边界条件（k<=0、k>n、空表）

复杂度分析（L2）

• 能分析顺序表操作的时间复杂度
• 能分析链表操作的时间复杂度
• 能分析算法的空间复杂度

8.2 自测问题

概念理解题（5道）

1. Q： 顺序表和链表的主要区别是什么？ A： 顺序表采用连续内存存储，支持随机访问；链表采用离散内存存储，只能顺序访问。
2. Q： 头结点的作用是什么？ A： 统一空表和非空表的处理、统一插入删除操作、方便遍历。
3. Q： 循环链表和普通链表的区别是什么？ A： 循环链表没有NULL指针，最后一个结点的next指向头结点；普通链表的最后一个结点的next为NULL。
4. Q： 双指针法的原理是什么？ A： 使用两个指针在链表上移动，通过两个指针的相对位置或移动速度来解决问题。
5. Q： 什么是"原地逆置"？ A： 在不申请额外存储空间（空间复杂度O(1)）的前提下，将线性表中的元素顺序反转。

公式应用题（5道）

1. Q： 顺序表插入操作的平均时间复杂度是多少？ A： O(n)，平均需要移动n/2个元素。
2. Q： 顺序表删除操作的平均时间复杂度是多少？ A： O(n)，平均需要移动(n-1)/2个元素。
3. Q： 链表按位查找的平均时间复杂度是多少？ A： O(n)，平均需要遍历(n-1)/2个结点。
4. Q： 双指针法找倒数第k个结点的时间复杂度是多少？ A： O(n)，只需要遍历一次链表。
5. Q： 有序合并的时间复杂度是多少？ A： O(m+n)，m和n分别是两个链表的长度。

综合分析题（3道）

1. Q： 如何选择合适的存储结构？ A： 频繁访问、少量插入删除 → 顺序表；频繁插入删除、少量访问 → 链表。
2. Q： 如何判断单链表是否有环？ A： 使用快慢指针法，快指针每次走2步，慢指针每次走1步，如果有环，快慢指针一定会相遇。
3. Q： 如何将两个递增有序链表合并为一个递减有序链表？ A： 使用头插法，依次比较两个链表的当前最小元素，将较小的元素用头插法插入结果链表。

易错辨析题（2道）

1. Q： "带头结点的单链表为空"的条件是什么？ A： head->next == NULL（不是head == NULL）
2. Q： "循环单链表为空"的条件是什么？ A： head->next == head（不是head->next == NULL）

8.3 完成度评估

整体掌握程度评估：

• 优秀（90分以上）： 继续下一章
• 良好（75-89分）： 分析错题，重点复习薄弱环节
• 及格（60-74分）： 系统复习本章，重点练习代码实现
• 不及格（60分以下）： 从DS-01-01重新学习

下一步学习建议：

• 如果选择题错误率高：重点复习基本概念，制作对比表格
• 如果算法题得分低：重点练习双指针法、有序合并、原地逆置
• 如果复杂度分析错误：重点复习时间复杂度的计算方法

在这里插入图片描述