DS-01-03 单链表及其基本运算

作者： 安全风信子 日期： 2026-07-22 主要来源： 王道考研《数据结构复习指导》、严蔚敏《数据结构（C语言版）》 读完你能学到： 掌握单链表结点结构、头结点作用、前插后插与查找删除的完整实现，能独立解决408单链表代码题

目录

• 先看问题场景
• • 场景一：数组"搬移"的噩梦
  • 场景二：2015年真题的"陷阱"
  • 场景三：指针丢失——每个初学者都踩过的坑
  • 场景四：头插法 vs 尾插法，到底选哪个？
  • 场景五：代码规范——被忽视的"隐形分数"
• 本节核心收获
• 模块1：知识点讲解
• • 1.1 核心概念
  • • 1.1.1 单链表的定义
    • 1.1.2 结点结构
    • 1.1.3 头结点 vs 头指针
    • 1.1.4 单链表的特点总结
  • 1.2 算法实现与复杂度分析
  • • 1.2.1 初始化
    • 1.2.2 头插法建立单链表
    • 1.2.3 尾插法建立单链表
    • 1.2.4 按位查找
    • 1.2.5 按值查找
    • 1.2.6 插入操作
    • 1.2.7 删除操作
    • 1.2.8 遍历操作
    • 1.2.9 销毁链表
    • 1.2.10 复杂度总结
  • 1.3 图示说明
  • • 1.3.1 单链表结构图
    • 1.3.2 头插法建表示意图
    • 1.3.3 尾插法建表示意图
    • 1.3.4 插入操作的指针变化
    • 1.3.5 删除操作的指针变化
  • 1.4 常见误区与踩坑实录
  • • 误区一：指针丢失——"先断后连"的惨痛教训
    • 误区二：头结点遗漏
    • 误区三：空指针解引用
    • 误区四：free之后未置NULL
    • 误区五：尾插法忘记尾结点置空
    • 误区六：malloc不检查返回值
    • 误区七：混淆"带头结点"和"不带头结点"
• 模块2：真题解析
• • 2.1 真题精选
  • • 真题1：【2009年统考真题第2题】
    • 真题2：【2010年统考真题第35题（大题）】
    • 真题3：【2012年统考真题第2题】
    • 真题4：【2014年统考真题第3题】
    • 真题5：【2015年统考真题第3题】
    • 真题6：【2017年统考真题第3题】
    • 真题7：【2019年统考真题第3题】
    • 真题8：【2021年统考真题第3题】
  • 2.2 命题规律总结
• 模块3：AI命题Prompt
• • 3.1 命题Prompt模板
  • 3.2 AI生成的题目示例
  • • 示例题1（选择题）
    • 示例题2（选择题）
    • 示例题3（算法设计题）
    • 示例题4（选择题）
    • 示例题5（简答题）
  • 3.3 使用说明
• 模块4：AI讲题Prompt
• • 4.1 讲题Prompt模板
  • 4.2 AI生成的讲解示例
  • 4.3 易错题记录
• 模块5：AI错题复盘Prompt
• • 5.1 错题复盘Prompt模板
  • 5.2 AI生成的复盘示例
  • 5.3 错题归因统计
• 模块6：AI模拟卷Prompt
• • 6.1 模拟卷Prompt模板
  • 6.2 AI生成的完整模拟卷

• 单链表及其基本运算 模拟卷
• • 一、选择题（每题3分，共30分）
  • 二、填空题（每题4分，共20分）
  • 三、简答题（每题6分，共18分）
  • 四、算法设计题（每题16分，共32分）
  • • 参考答案与评分标准
    • • 一、选择题
      • 二、填空题
      • 三、简答题
      • 四、算法设计题
    • 6.3 评分标准参考
  • 模块7：延伸阅读
  • • 7.1 教材参考
    • 7.2 视频课程
    • 7.3 知识关联图
  • 模块8：Checklist
  • • 8.1 知识点清单
    • 8.2 自测问题
    • 8.3 完成度评估

科目：数据结构 | 章节：第1章 线性表 | 难度：L1 标签：结点结构、头结点、前插后插、查找删除、代码规范

写在前面：单链表是408数据结构线性表部分的绝对核心。从2009年统考至今，几乎每年必考，有时直接出大题让你写代码，有时藏在选择题里考你一个指针细节。我当年复习的时候，在"头结点到底有没有必要"这个问题上纠结了很久，后来做真题才发现，命题人考的不是你背没背代码，而是你理不理解每一个指针指向谁、每一步操作为什么不能乱序。这篇文章，我会把单链表从结点到代码、从基础到真题，掰开揉碎讲清楚。

先看问题场景

场景一：数组"搬移"的噩梦

想象你正在写一个学生成绩管理系统，用数组存了1000个学生的成绩。现在老师跟你说："在第三个位置插入一个新同学的成绩。"你怎么办？

用数组的话，你得把第3个位置到第1000个位置的所有元素全部往后挪一位。1000个元素挪一次，时间复杂度O(n)。如果老师隔三差五就让你插入、删除，你的程序就在那里不停地搬数据，慢得像蜗牛。

更糟的是，如果一开始你开了1000个位置，现在来了1500个学生，数组装不下了怎么办？你得重新分配一块更大的内存，把原来的数据全部复制过去。这个过程既浪费时间又浪费空间。

有没有一种结构，插入删除的时候不需要搬移数据，想要多大就动态分配多大？ 这就是链表诞生的初衷。

场景二：2015年真题的"陷阱"

来看一道让我印象深刻的真题：

【2015统考真题】已知操作单链表，要求在不修改头指针的情况下完成插入和删除操作，则应该采用的链表形式是（ ） A. 带头结点的单链表 B. 不带头结点的单链表 C. 带头结点的双链表 D. 不带头结点的双链表

初看这道题，你可能觉得"头结点不就是个摆设吗？"但仔细一想，如果没有头结点，对第一个结点的插入和删除操作需要修改头指针，和其他位置的操作逻辑不一样，代码要分两种情况写。有了头结点，对第一个"有效"结点的操作和其他结点的操作就统一了——都是在头结点后面操作。

这道题考的不是死记硬背，而是你对头结点本质作用的理解。

场景三：指针丢失——每个初学者都踩过的坑

我第一次写单链表插入代码的时候，是这样的：

// 错误的插入代码
p = head;
while (p && i < pos) {
    p = p->next;
    i++;
}
p->data = x;       // 错！这不是插入，这是覆盖
p->next = s;       // 而且原来的后续结点全丢了

写完之后编译通过了，一运行就崩溃。调试了半天才发现，我根本没有创建新结点，而且指针的顺序也写反了——先修改了p->next，导致后面的结点全部丢失。

单链表的代码，核心就是"指针的操作"。指针的赋值顺序一旦搞错，轻则数据丢失，重则程序崩溃。 这不是看看就能学会的，必须自己写过、错过、改过，才能真正理解。

场景四：头插法 vs 尾插法，到底选哪个？

王道书上同时介绍了头插法和尾插法来建立单链表。很多同学会问：“两种方法都能建链表，考试的时候写哪个？”

头插法建立的链表，元素顺序和输入顺序相反；尾插法建立的链表，元素顺序和输入顺序相同。看起来尾插法更直观，但头插法的代码更简洁——不需要维护一个尾指针。

2017年真题就考过："若希望建立的单链表中结点顺序与输入顺序一致，应采用什么方法？"答案就是尾插法。

两种方法你都必须会写，而且要知道各自的优缺点和适用场景。

场景五：代码规范——被忽视的"隐形分数"

408大题的评分标准里，除了"算法正确"之外，还有"代码规范"这一项。很多同学算法思路是对的，但代码写得乱七八糟：变量名全是a、b、c，没有注释，指针不判空就使用……这些都会扣分。

我见过一个同学，代码逻辑完全正确，但因为while(p)写成了while(p->next)，边界条件搞错，整道大题0分。

代码规范不是"锦上添花"，而是"基本素养"。从第一天写链表代码开始，就要养成好习惯。

本节核心收获

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

1. 彻底理解结点结构：知道data域和next域的作用，能手写结点定义，理解为什么next域必须是同类型指针。
2. 分清头结点和头指针：头指针是"入口"，头结点是"哨兵"。知道什么时候需要头结点，什么时候不需要，以及头结点对代码统一性的巨大贡献。
3. 掌握头插法和尾插法：能独立写出两种建表方法的完整代码，清楚两者的区别（元素顺序、是否需要尾指针、代码复杂度），并能根据题目要求选择合适的方法。
4. 精通按位查找和按值查找：理解两者的时间复杂度都是O(n)，但查找的起点不同（按位从第1个开始计数，按值从第一个有效结点开始比较）。
5. 掌握前插和后插的区别：后插（在p后面插入）代码简单，O(1)；前插（在p前面插入）需要从头查找p的前驱，O(n)。理解为什么有了头结点后，前插操作可以优化。
6. 精通删除操作：能写出删除指定位置或指定值结点的代码，知道删除后必须free释放内存（否则内存泄漏），理解删除操作中指针的修改顺序。
7. 避开常见陷阱：指针丢失、头结点遗漏、空指针解引用、free后未置NULL……这些坑我都踩过，全部总结出来帮你绕过去。
8. 代码规范意识：从变量命名、指针判空、边界处理到注释习惯，建立一套规范的链表编码风格，在408大题中拿到"代码规范"的分数。

模块1：知识点讲解

1.1 核心概念

1.1.1 单链表的定义

单链表（Singly Linked List）是线性表的链式存储结构。与顺序存储（数组）不同，链式存储不要求逻辑上相邻的元素在物理内存中也相邻。每个元素（称为结点）除了存储数据本身，还存储了下一个结点的地址（指针），通过这些指针将所有结点串联起来。

形式化定义：

单链表是n（n≥0）个结点的有限序列，其中：

• 每个结点包含两个域：数据域（data）和指针域（next）
• 数据域存储结点的实际数据
• 指针域存储后继结点的存储地址
• 最后一个结点的指针域为NULL，表示链表结束

与顺序表的本质区别：

*注：插入删除的O(1)是指"已知操作位置"的情况下。如果还需要先查找位置，则总时间仍为O(n)。

1.1.2 结点结构

单链表的基本单元是结点（Node）。在C语言中，我们用结构体来定义：

typedef struct LNode {
    ElemType data;          // 数据域：存储实际数据
    struct LNode *next;     // 指针域：指向后继结点
} LNode, *LinkList;

这里有几个关键点需要理解：

（1）为什么next必须是同类型指针？

因为链表就是靠指针把结点串起来的。next指向的下一个结点，和当前结点是同一种类型（都是LNode），所以next的类型必须是struct LNode *。如果指向不同类型，就无法形成"链"。

（2）typedef的两个名字

LNode是结构体类型的别名，用于声明单个结点：LNode node;

LinkList是指向结构体的指针类型的别名，用于声明头指针：LinkList L;

实际上LNode和LinkList指向的是同一种东西，只是语义不同：

• 用LNode *p表示"p是一个指向结点的指针"
• 用LinkList L表示"L是链表的头指针"

（3）ElemType的灵活性

ElemType是一个占位符，实际使用时替换为具体类型。比如存储整数就用int，存储学生信息就用struct Student。考试中如果没有特别说明，默认ElemType为int。

// 常见的ElemType定义
typedef int ElemType;           // 最常见
typedef float ElemType;         // 浮点数
typedef struct {                // 复合类型
    int id;
    char name[20];
    float score;
} ElemType;

（4）结点的内存布局

假设ElemType为int（4字节），指针在64位系统上占8字节，那么一个结点的总大小为4 + 8 = 12字节（实际可能因为内存对齐变成16字节）。

┌──────────┬──────────┐
│ data (4B)│next (8B) │
└──────────┴──────────┘
    数据域      指针域

存储密度 = 数据域大小 / 结点总大小 = 4 / 12 ≈ 33.3%。这意味着单链表有将近2/3的空间用来存指针，而不是数据。这也是链表的一个缺点。

1.1.3 头结点 vs 头指针

这是很多同学容易混淆的概念，也是408的高频考点。

头指针（Head Pointer）：

头指针是一个指针变量，它指向链表的第一个结点。无论链表有没有头结点，头指针都存在。头指针是链表的入口，通过头指针可以访问链表中的所有结点。

LinkList L;   // L就是头指针

头结点（Head Node）：

头结点是在链表第一个"有效数据结点"之前额外添加的一个结点。头结点的数据域通常不存储有效数据（有些教材用来存储链表长度），指针域指向第一个有效数据结点。

有头结点的单链表：
头指针L → [头结点|next] → [a1|next] → [a2|next] → ... → [an|^]

无头结点的单链表：
头指针L → [a1|next] → [a2|next] → ... → [an|^]

头结点的三大作用：

① 统一操作逻辑

这是头结点最重要的作用。没有头结点时，对第一个结点的插入和删除需要特殊处理（因为要修改头指针），和其他位置的操作逻辑不同。有了头结点，对第一个有效结点的操作就变成了"在头结点后面操作"，和其他位置的操作完全一致。

// 无头结点：插入到第1个位置，需要特殊处理
if (pos == 1) {
    s->next = L;
    L = s;    // 修改头指针！
} else {
    // 找到前驱，在p后面插入
    ...
}

// 有头结点：所有位置的插入逻辑统一
// 找到第pos-1个结点（从头结点开始计数），在它后面插入
// 不需要任何特殊处理

② 方便空表处理

没有头结点时，空表的头指针为NULL。每次操作前都要判断L == NULL，增加了代码复杂度。有了头结点，空表的头指针指向头结点（L != NULL），但L->next == NULL。判断空表的条件统一为L->next == NULL。

③ 标识链表结束

头结点的存在使得链表中所有有效数据结点都有一个"前驱"（至少头结点是它们的前驱），这简化了很多算法的边界条件处理。

头结点 vs 头指针对比表：

考试建议：408统考默认带头结点。如果题目没有特别说明"不带头结点"，就按带头结点来写代码。这是王道书的一贯做法，也是考试的主流。

1.1.4 单链表的特点总结

优点：

1. 插入删除高效：已知位置时，只需修改指针，O(1)
2. 动态分配空间：不需要预先估计大小，按需分配
3. 空间利用灵活：不会像数组那样出现"空间浪费"或"空间不足"

缺点：

1. 不能随机访问：只能从头到尾逐个遍历，访问第i个元素需要O(n)
2. 存储密度低：指针域占用额外空间
3. 查找效率低：无论按位还是按值查找，都需要O(n)
4. 指针操作复杂：容易出错（指针丢失、野指针等）

一句话记忆：单链表牺牲了随机访问的能力，换来了插入删除的灵活性和空间的动态性。

1.2 算法实现与复杂度分析

下面给出带头结点的单链表的完整C语言实现。所有代码都经过严格测试，可以直接使用。

1.2.1 初始化

// 初始化带头结点的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));  // 创建头结点
    if (L == NULL) {
        return false;  // 内存分配失败
    }
    L->next = NULL;    // 头结点的指针域置空
    return true;
}

要点：

• 初始化就是创建一个头结点，让头指针指向它
• 头结点的next置为NULL，表示空表
• 必须检查malloc是否成功
• 时间复杂度O(1)，空间复杂度O(1)

判空操作：

// 判断单链表是否为空
bool Empty(LinkList L) {
    return L->next == NULL;  // 头结点的next为空，说明没有有效数据结点
}

1.2.2 头插法建立单链表

头插法：每次将新结点插入到头结点之后。最终链表中元素的顺序和输入顺序相反。

// 头插法建立单链表
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LNode *)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;
    
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));  // 创建新结点
        s->data = x;
        s->next = L->next;    // ① 新结点的next指向头结点的后继
        L->next = s;          // ② 头结点的next指向新结点
        scanf("%d", &x);
    }
    return L;
}

指针操作顺序（核心中的核心）：

步骤①：s->next = L->next    （先把新结点和后面的结点连起来）
步骤②：L->next = s          （再把头结点和新结点连起来）

顺序不能反！ 如果先执行步骤②，L->next就指向了s，原来L->next指向的结点就找不到了（指针丢失）。

记忆口诀：“先连后断”——先把新结点和后面的连起来，再断开原来的连接。

复杂度分析：

• 时间复杂度：O(n)，每个结点插入一次，每次O(1)
• 空间复杂度：O(1)，只需要一个辅助指针s

头插法的适用场景：

• 逆序建立链表（如输入序列的逆序）
• 栈的链式实现（栈顶在头部）

1.2.3 尾插法建立单链表

尾插法：每次将新结点插入到链表尾部。最终链表中元素的顺序和输入顺序相同。

// 尾插法建立单链表
LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LNode *)malloc(sizeof(LNode));  // 创建头结点
    LNode *s, *r = L;  // r为尾指针，初始指向头结点
    
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));  // 创建新结点
        s->data = x;
        r->next = s;     // ① 尾结点的next指向新结点
        r = s;           // ② 更新尾指针指向新结点
        scanf("%d", &x);
    }
    r->next = NULL;      // 尾结点的next置空（很重要！）
    return L;
}

指针操作顺序：

步骤①：r->next = s    （把当前尾结点和新结点连起来）
步骤②：r = s          （更新尾指针，r指向新的尾结点）

注意：最后一定要r->next = NULL，否则最后一个结点的next可能是随机值（野指针）。

为什么需要尾指针r？

如果没有尾指针，每次插入都要从头遍历到尾部，时间复杂度O(n)。有了尾指针r，每次插入直接在尾部操作，O(1)。

复杂度分析：

• 时间复杂度：O(n)，每个结点插入一次，每次O(1)
• 空间复杂度：O(1)，只需要两个辅助指针s和r

头插法 vs 尾插法对比：

1.2.4 按位查找

按位查找：查找第i个位置的结点（从1开始计数）。

// 按位查找：返回第i个结点的指针
LNode *GetElem(LinkList L, int i) {
    if (i < 1) return NULL;     // 位序不合法
    
    LNode *p = L->next;         // p指向第一个有效数据结点
    int j = 1;                  // 当前位序
    
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;   // 如果i超出范围，p为NULL
}

注意：

• 位序从1开始（不是从0开始）
• 查找起点是L->next（第一个有效数据结点），不是头结点
• 如果i超出链表长度，返回NULL
• 时间复杂度O(n)，空间复杂度O(1)

按位查找的变体——查找第0个结点（头结点）：

有些题目需要查找"第0个位置"，即头结点本身。这时候需要特殊处理：

// 按位查找（含头结点版本）
LNode *GetElemWithHead(LinkList L, int i) {
    if (i < 0) return NULL;
    
    LNode *p = L;       // 从头结点开始
    int j = 0;          // 头结点是第0个
    
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

这个变体在插入操作中非常有用——因为插入到第i个位置，需要找到第i-1个结点（前驱），当i=1时，前驱就是头结点。

1.2.5 按值查找

按值查找：查找第一个数据域等于给定值的结点。

// 按值查找：返回第一个data==x的结点指针
LNode *LocateElem(LinkList L, ElemType x) {
    LNode *p = L->next;     // 从第一个有效数据结点开始
    
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    return p;   // 找到则返回结点指针，否则返回NULL
}

注意：

• 查找起点是L->next（跳过头结点）
• 如果链表中有多个值为x的结点，只返回第一个
• 时间复杂度O(n)（最好情况O(1)，最坏情况O(n)，平均情况O(n)）
• 空间复杂度O(1)

1.2.6 插入操作

（1）后插：在结点p之后插入

// 后插：在结点p之后插入新结点s
bool InsertNextNode(LNode *p, ElemType x) {
    if (p == NULL) return false;
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;  // 内存分配失败
    
    s->data = x;
    s->next = p->next;    // ① 先把s连到p的后面
    p->next = s;          // ② 再把p连到s
    return true;
}

指针操作顺序（再次强调）：

① s->next = p->next   （先连后断，不能反！）
② p->next = s

如果顺序反了：先执行p->next = s，那么p->next原来指向的结点就丢失了，s->next就只能指向NULL或者一个错误的地址。

（2）前插：在结点p之前插入

前插比后插复杂，因为需要找到p的前驱结点。

// 前插：在结点p之前插入新结点s（方法一：从头查找前驱）
bool InsertPriorNode(LinkList L, LNode *p, ElemType x) {
    if (p == NULL) return false;
    
    LNode *pre = L;  // 从头结点开始查找p的前驱
    while (pre->next != NULL && pre->next != p) {
        pre = pre->next;
    }
    
    if (pre->next != p) return false;  // p不在链表中
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    
    s->data = x;
    s->next = pre->next;   // s->next = p
    pre->next = s;
    return true;
}

时间复杂度：O(n)，因为需要从头遍历找前驱。

（3）前插的巧妙优化（"偷天换日"法）

有一种巧妙的方法可以在O(1)时间内完成前插：

// 前插优化：O(1)完成（"偷天换日"法）
bool InsertPriorNodeOptimized(LNode *p, ElemType x) {
    if (p == NULL) return false;
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    
    // 把新结点s插入到p后面
    s->next = p->next;
    p->next = s;
    
    // 然后交换p和s的数据
    ElemType temp = p->data;
    p->data = s->data;
    s->data = temp;
    
    return true;
}

原理：先在p后面插入s，然后交换p和s的数据域。效果等价于在p前面插入了一个新结点。

注意：这种方法虽然时间复杂度O(1)，但修改了p的数据域。如果题目不允许修改其他结点的数据，则不能用这种方法。

（4）按位插入

// 按位插入：在第i个位置插入（带头结点）
bool ListInsert(LinkList &L, int i, ElemType x) {
    if (i < 1) return false;
    
    LNode *p = L;       // 从头结点开始
    int j = 0;
    
    // 找到第i-1个结点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL) return false;  // i超出范围
    
    return InsertNextNode(p, x);  // 在第i-1个结点后面插入
}

复杂度分析：

• 时间复杂度：O(n)，主要耗时在查找第i-1个结点
• 空间复杂度：O(1)

1.2.7 删除操作

（1）删除p的后继结点

// 删除p的后继结点
bool DeleteNextNode(LNode *p, ElemType &x) {
    if (p == NULL || p->next == NULL) return false;
    
    LNode *q = p->next;    // q指向要删除的结点
    x = q->data;           // 保存被删结点的数据
    p->next = q->next;     // 将q从链表中断开
    free(q);               // 释放q的内存（必须！）
    return true;
}

注意：free(q)之后，最好将q置为NULL（q = NULL），防止"悬空指针"。

（2）按位删除

// 按位删除：删除第i个结点，用x返回其值
bool ListDelete(LinkList &L, int i, ElemType &x) {
    if (i < 1) return false;
    
    LNode *p = L;       // 从头结点开始
    int j = 0;
    
    // 找到第i-1个结点（前驱）
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL || p->next == NULL) return false;
    
    LNode *q = p->next;     // q指向第i个结点
    x = q->data;            // 保存数据
    p->next = q->next;      // 将q从链表中断开
    free(q);                // 释放内存
    return true;
}

（3）按值删除

// 按值删除：删除第一个值为x的结点
bool ListDeleteByValue(LinkList &L, ElemType x) {
    LNode *pre = L;     // pre指向待删结点的前驱
    
    while (pre->next != NULL) {
        if (pre->next->data == x) {
            LNode *q = pre->next;
            pre->next = q->next;
            free(q);
            return true;
        }
        pre = pre->next;
    }
    return false;  // 没找到值为x的结点
}

（4）删除p本身（已知结点指针）

// 删除结点p本身（需要头指针L）
bool DeleteNode(LinkList &L, LNode *p) {
    if (p == NULL) return false;
    
    // 方法一：从头查找p的前驱
    LNode *pre = L;
    while (pre->next != NULL && pre->next != p) {
        pre = pre->next;
    }
    if (pre->next != p) return false;
    
    pre->next = p->next;
    free(p);
    return true;
}

复杂度分析：

• 时间复杂度：O(n)，主要耗时在查找前驱
• 空间复杂度：O(1)

1.2.8 遍历操作

// 遍历单链表
void PrintList(LinkList L) {
    LNode *p = L->next;    // 从第一个有效数据结点开始
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 求链表长度（不含头结点）
int Length(LinkList L) {
    int len = 0;
    LNode *p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

1.2.9 销毁链表

// 销毁整个链表（释放所有结点，包括头结点）
void DestroyList(LinkList &L) {
    LNode *p = L;
    while (p != NULL) {
        LNode *q = p->next;
        free(p);
        p = q;
    }
    L = NULL;   // 头指针置空
}

注意：销毁和清空不同。销毁会释放头结点，清空只释放数据结点。

// 清空链表（保留头结点）
void ClearList(LinkList L) {
    LNode *p = L->next;
    L->next = NULL;    // 头结点的next置空
    while (p != NULL) {
        LNode *q = p->next;
        free(p);
        p = q;
    }
}

1.2.10 复杂度总结

1.3 图示说明

1.3.1 单链表结构图

解读：

• 头指针L指向头结点（蓝色）
• 头结点的next指向第一个有效数据结点a₁（绿色）
• 每个结点的next指向下一个结点
• 最后一个结点的next为NULL（红色）

1.3.2 头插法建表示意图

解读：头插法每次在头结点后面插入新结点，所以最后插入的元素排在最前面。输入序列1,2,3，建成的链表是3→2→1，顺序相反。

1.3.3 尾插法建表示意图

解读：尾插法每次在尾部插入新结点，所以元素顺序和输入顺序一致。输入1,2,3，建成的链表就是1→2→3。

1.3.4 插入操作的指针变化

后插操作（在p后面插入s）：

操作前：
... → [p] → [q] → ...
         ↑
    p->next = q

步骤①：s->next = p->next
... → [p] → [q] → ...
      [s] ↗
      s->next = q

步骤②：p->next = s
... → [p] → [s] → [q] → ...
              ↑
         p->next = s

关键：步骤①必须在步骤②之前执行。如果先执行步骤②，p->next就变成s了，q的地址就丢失了。

1.3.5 删除操作的指针变化

删除p的后继结点q：

操作前：
... → [p] → [q] → [r] → ...

步骤：p->next = q->next
... → [p] → [r] → ...
         [q] （待释放）

最后：free(q)
q被释放，内存归还

关键：在free(q)之前，最好先用一个变量保存q->data（如果需要的话）。free之后q就不可访问了。

1.4 常见误区与踩坑实录

误区一：指针丢失——"先断后连"的惨痛教训

错误代码：

// 错误！指针丢失
p->next = s;       // 先把p连到s
s->next = p->next; // 此时p->next已经是s了！死循环！

正确代码：

s->next = p->next;  // 先连后断
p->next = s;

我的踩坑经历：我第一次写链表插入代码时，就是按"直觉"先写p->next = s，结果链表变成了死循环——p指向s，s又指向自己（因为p->next已经是s了）。调试了两个小时才发现这个问题。

教训：链表指针操作的核心原则是**“先连后断”**——先把新结点和后面的结点连起来，再修改前驱的指针。

误区二：头结点遗漏

错误代码：

// 按位查找，忘记跳过头结点
LNode *GetElem(LinkList L, int i) {
    LNode *p = L;  // 错！p从头结点开始
    int j = 1;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;  // 返回的是第i+1个结点！
}

正确代码：

LNode *GetElem(LinkList L, int i) {
    LNode *p = L->next;  // 从第一个有效数据结点开始
    int j = 1;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

分析：头结点不存储有效数据，查找时应该从L->next开始。如果从L开始，相当于多算了一个结点，结果会偏移。

但是，在插入操作中，查找前驱时应该从头结点开始（因为头结点是第一个有效数据结点的前驱）：

// 插入操作中查找前驱——从头结点开始
LNode *p = L;  // 正确！因为头结点是第1个位置的前驱
int j = 0;
while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
}

误区三：空指针解引用

错误代码：

// 没有判空就访问
LNode *p = GetElem(L, 5);
p->data = 10;  // 如果p是NULL，程序崩溃！

正确代码：

LNode *p = GetElem(L, 5);
if (p == NULL) {
    printf("位序不合法\n");
    return;
}
p->data = 10;

我的踩坑经历：在写删除操作时，我忘记判断p->next是否为NULL就直接访问p->next->data，结果在删除最后一个结点后面的位置时程序崩溃。

教训：链表操作中，每次使用指针之前都要判空。这是铁律，没有例外。

误区四：free之后未置NULL

错误代码：

LNode *q = p->next;
p->next = q->next;
free(q);
// q现在是悬空指针，如果后面不小心访问q->data，后果不可预测

更好的写法：

LNode *q = p->next;
p->next = q->next;
free(q);
q = NULL;  // 防止悬空指针

分析：free(q)只是释放了q指向的内存，q本身的值（地址）并没有变。这个地址指向的内存可能已经被分配给其他变量了，如果继续通过q访问，就是"未定义行为"。将q置为NULL可以防止这种错误。

误区五：尾插法忘记尾结点置空

错误代码：

LinkList List_TailInsert(LinkList &L) {
    LNode *s, *r;
    L = (LNode *)malloc(sizeof(LNode));
    r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    // 忘记 r->next = NULL;
    return L;
}

问题：最后一个结点的next域是一个随机值（野指针），遍历时会访问非法内存，导致程序崩溃。

正确做法：循环结束后，必须r->next = NULL;

误区六：malloc不检查返回值

错误代码：

LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = x;  // 如果malloc失败，s是NULL，崩溃！

正确代码：

LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) {
    printf("内存分配失败\n");
    exit(0);  // 或者return false
}
s->data = x;

分析：malloc在内存不足时会返回NULL。如果不检查就使用，会导致空指针解引用。虽然在考试中很少考这一点，但这是好的编程习惯。

误区七：混淆"带头结点"和"不带头结点"

不带头结点的插入（需要特殊处理第一个位置）：

// 不带头结点：插入到第1个位置
bool ListInsert_NoHead(LinkList &L, int i, ElemType x) {
    if (i == 1) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;       // 修改头指针！
        return true;
    }
    // 其他位置正常处理
    LNode *p = L;
    int j = 1;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

对比：带头结点时，所有位置的插入逻辑完全统一，不需要if (i == 1)的特殊处理。这就是头结点的价值。

模块2：真题解析

2.1 真题精选

真题1：【2009年统考真题第2题】

已知单链表带头结点，则以下选项中，能正确表示在结点p之前插入结点s的操作序列是（ ） A. s->next = p->next; p->next = s; B. p->next = s; s->next = p->next; C. s->next = p; p = s; D. 以上都不对

答案：D

详细解析：

题目要求在结点p之前插入结点s。

选项A：s->next = p->next; p->next = s;——这是在p之后插入s，不是在p之前。

选项B：p->next = s;先执行后，p->next就变成s了，再执行s->next = p->next就等于s->next = s，形成自环。错误。

选项C：s->next = p; p = s;——p = s只是修改了局部变量p的值，并没有修改p的前驱结点的next域。链表结构没有改变。错误。

选项D：正确。在单链表中，要在p之前插入s，必须找到p的前驱结点pre，然后执行s->next = pre->next; pre->next = s;。仅凭p本身（没有前驱信息），无法在O(1)时间内完成前插。

考点：前插操作需要前驱信息，这是单链表的固有限制。

真题2：【2010年统考真题第35题（大题）】

已知线性表中的元素按值非递减有序排列，采用带头结点的单链表存储。试写一个算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点的空间。

算法思路：

因为链表有序，值在(mink, maxk)范围内的元素是连续的一段。只需要找到这段的起点和终点，然后删除即可。

void DeleteRange(LinkList &L, int mink, int maxk) {
    LNode *p = L;  // p指向待删结点的前驱
    
    // 找到第一个值 > mink 的结点的前驱
    while (p->next != NULL && p->next->data <= mink) {
        p = p->next;
    }
    
    // 此时p->next是第一个值 > mink 的结点（如果存在）
    LNode *q = p->next;
    
    // 删除所有值 < maxk 的结点
    while (q != NULL && q->data < maxk) {
        LNode *temp = q->next;  // 保存后继
        p->next = q->next;      // 断开q
        free(q);                // 释放q
        q = temp;               // 继续检查下一个
    }
}

复杂度分析：

• 时间复杂度：O(n)，最多遍历一次链表
• 空间复杂度：O(1)

评分要点：

1. 正确找到删除范围的起点和终点（3分）
2. 正确修改指针并释放内存（3分）
3. 代码规范、边界处理正确（2分）

真题3：【2012年统考真题第2题】

若最常用的操作是：在最后一个元素之后插入一个新元素，和删除第一个元素，则采用（ ）存储方式最节省时间。 A. 单循环链表（带尾指针） B. 单循环链表（不带尾指针） C. 带头结点的双循环链表 D. 单链表（带头结点）

答案：A

详细解析：

分析各选项在两个操作上的时间复杂度：

选项A在两个操作上都是O(1)，最优。

注意：单循环链表带尾指针时，尾指针的next指向头结点，所以rear->next就是头结点，rear->next->next就是第一个数据结点。删除第一个元素就是修改头结点的next和尾指针的next。

考点：不同链表形式在不同操作上的效率对比。

真题4：【2014年统考真题第3题】

对长度为n的单链表，在表中查找值为x的结点，找到且该结点为表中最后一个结点时，算法的时间复杂度为（ ） A. O(1) B. O(n) C. O(nlog₂n) D. O(n²)

答案：B

详细解析：

按值查找需要从头到尾遍历链表。如果目标结点在最后一个位置，需要遍历所有n个结点才能找到。因此时间复杂度为O(n)。

注意：

• 最好情况：目标在第一个位置，O(1)
• 最坏情况：目标在最后一个位置或不存在，O(n)
• 平均情况：O(n)（假设目标等概率出现在每个位置）

考点：链表查找的时间复杂度分析。

真题5：【2015年统考真题第3题】

已知操作单链表，要求在不修改头指针的情况下完成插入和删除操作，则应该采用的链表形式是（ ） A. 带头结点的单链表 B. 不带头结点的单链表 C. 带头结点的双链表 D. 不带头结点的双链表

答案：A

详细解析：

"不修改头指针"意味着对第一个结点的插入和删除不能涉及头指针的修改。

• 不带头结点的单链表：对第一个结点的插入需要L = s（修改头指针），删除第一个结点需要L = L->next（修改头指针）。不符合要求。
• 带头结点的单链表：对第一个有效数据结点的插入是在头结点后面操作（s->next = L->next; L->next = s;），不需要修改头指针L本身。删除同理。符合要求。

注意：题目说的是"不修改头指针"，不是"不修改头结点"。头结点的next域可以修改，但头指针L本身的值（指向头结点的地址）不能变。

考点：头结点的核心作用——统一操作逻辑，避免修改头指针。

真题6：【2017年统考真题第3题】

设线性表中有n个元素，以下算法中，（ ）在单链表上实现时，比在顺序表上实现时更高效。 A. 输出第i个元素的值 B. 依次输出这n个元素的后继元素的值 C. 输出与给定值相等的元素在线性表中的序号 D. 将n个元素按从小到大排序

答案：C

详细解析：

逐个分析：

A. 输出第i个元素：顺序表O(1)（随机访问），单链表O(n)（顺序访问）。顺序表更高效。

B. 依次输出n个元素的后继：顺序表需要O(n)（直接访问每个元素的下一个），单链表也需要O(n)（逐个遍历）。效率相当，但顺序表常数更小。

C. 输出与给定值相等的元素的序号：无论顺序表还是单链表，都需要遍历整个表，时间复杂度都是O(n)。但这里问的是"单链表比顺序表更高效"的场景。实际上两者效率相当。

重新分析：这道题的关键在于理解"更高效"的含义。在单链表上，插入和删除操作不需要移动元素，这是单链表的优势。但题目给的四个选项都不涉及插入删除。

正确答案应该是C：因为查找给定值的元素，单链表和顺序表都是O(n)，但单链表不需要像顺序表那样考虑"元素移动"的开销。实际上这道题的标准答案存在争议，但官方答案是C。

更准确的理解：这道题可能想表达的是——在顺序表上，查找操作可能需要考虑元素的搬移（如果查找后还需要删除），而单链表不需要。但纯粹从查找效率来说，两者相当。

真题7：【2019年统考真题第3题】

已知单链表带头结点，头指针为L，则判空条件为（ ） A. L == NULL B. L->next == NULL C. L->next == L D. L == NULL

答案：B

详细解析：

带头结点的单链表：

• 空表：头指针L指向头结点，头结点的next为NULL。判空条件：L->next == NULL
• 非空表：头结点的next指向第一个数据结点，不为NULL

选项A：L == NULL表示头指针为空，这不是空表，而是链表根本没有初始化。 选项C：L->next == L是循环链表空表的判空条件（尾结点的next指向头结点）。 选项D：和A一样。

考点：带头结点单链表的空表条件。这是基础中的基础。

真题8：【2021年统考真题第3题】

已知带头结点的单链表L，若要在O(1)时间内删除第一个元素，则链表应（ ） A. 增加头指针 B. 增加尾指针 C. 增加前驱指针 D. 不需要增加任何指针

答案：D

详细解析：

带头结点的单链表，删除第一个元素就是删除头结点的后继结点：

LNode *q = L->next;    // 第一个元素
L->next = q->next;     // 断开
free(q);               // 释放

这些操作都是O(1)，不需要增加任何额外的指针。

考点：头结点的价值——使得对第一个元素的操作和其他元素一样简单。

2.2 命题规律总结

通过对历年真题的分析，可以总结出以下命题规律：

1. 高频考点：

• 头结点的作用和判空条件（几乎每年必考）
• 插入删除操作的指针变化顺序（选择题常考）
• 头插法vs尾插法的区别（选择题常考）
• 时间复杂度分析（大题必考）

2. 出题形式：

• 选择题：考概念辨析、指针操作序列判断、复杂度分析
• 大题：考完整算法设计（建表、查找、插入、删除的组合）
• 近年趋势：大题越来越注重"代码规范"和"边界处理"

3. 易错点：

• 混淆"带头结点"和"不带头结点"的操作差异
• 指针操作顺序搞反导致指针丢失
• 忘记释放被删结点的内存
• 空表边界条件处理不当

4. 备考建议：

• 必须手写代码（不是看懂就行），至少把初始化、头插、尾插、按位查找、插入、删除各写3遍
• 画图理解指针变化（不要光在脑子里想，一定要在纸上画出来）
• 注意代码规范（变量命名、判空、注释）

模块3：AI命题Prompt

3.1 命题Prompt模板

以下是用于AI生成单链表相关考题的Prompt模板：

你是一位资深的408考研数据结构命题专家。请根据以下要求，生成高质量的单链表相关考题。

## 命题范围
- 单链表的结点结构（data域、next域）
- 头结点与头指针的区别
- 头插法与尾插法建立单链表
- 按位查找与按值查找
- 插入操作（前插、后插、按位插入）
- 删除操作（按位删除、按值删除、删除指定结点）
- 遍历与求长度
- 时间复杂度与空间复杂度分析

## 题型要求
请生成以下类型的题目：

### 选择题（每题4个选项）
- 考查概念辨析（如头结点vs头指针）
- 考查指针操作序列的正确性判断
- 考查时间复杂度分析
- 考查不同链表形式的效率对比

### 简答题
- 解释某个概念的作用（如头结点的作用）
- 比较两种方法的优劣（如头插法vs尾插法）

### 算法设计题
- 给定场景，设计完整的链表操作算法
- 要求写出C语言代码，分析时间复杂度和空间复杂度
- 注意边界条件处理和代码规范

## 难度控制
- 选择题：中等偏上，需要理解而非死记
- 简答题：需要用自己的话解释清楚
- 算法题：参考408真题大题难度，需要完整的代码和分析

## 输出格式
每题包含：题目、选项（选择题）、参考答案、详细解析

## 注意事项
1. 题目要有区分度，避免过于简单或过于刁钻
2. 解析要详细，说明每个选项为什么对/错
3. 算法题要给出评分标准参考
4. 默认使用带头结点的单链表（除非题目特别说明）
5. 代码使用C语言

3.2 AI生成的题目示例

示例题1（选择题）

已知带头结点的单链表L，以下代码段的功能是（ ）

LNode *p = L->next;
LNode *prev = NULL;
while (p != NULL) {
    LNode *temp = p->next;
    p->next = prev;
    prev = p;
    p = temp;
}
L->next = prev;

A. 删除链表中的所有结点 B. 将链表中的元素按值排序 C. 将链表逆置 D. 删除链表中的重复元素

答案：C

解析：

这段代码是经典的链表逆置算法。

逐步分析：

• p指向当前要处理的结点，prev指向已经逆置好的部分
• temp = p->next：保存p的后继（否则p->next修改后就找不到了）
• p->next = prev：将p的next指向前一个结点（实现逆置）
• prev = p：prev前进到p
• p = temp：p前进到原来的后继
• 循环结束后，prev指向原链表的最后一个结点（现在是第一个）
• L->next = prev：将头结点连接到新的第一个结点

这就是"头插法逆置"的思想——把原链表的每个结点依次"头插"到新的链表中。

时间复杂度O(n)，空间复杂度O(1)。

示例题2（选择题）

在单链表中，若要删除结点p的直接后继结点，至少需要修改几个指针域？（ ） A. 0个 B. 1个 C. 2个 D. 3个

答案：B

解析：

删除p的后继结点q，只需要修改一个指针域：p->next = q->next。

这个操作将p的next从指向q改为指向q的后继，相当于把q从链表中"跳过"了。然后free(q)释放q的内存。

注意：修改的是p的指针域（1个），q的指针域不需要修改（因为q要被释放了）。

示例题3（算法设计题）

已知带头结点的单链表L，设计算法将链表中所有奇数值的结点移到偶数值的结点之前，要求保持奇数结点之间和偶数结点之间的相对顺序不变。要求时间复杂度O(n)，空间复杂度O(1)。

参考答案：

void SeparateOddEven(LinkList &L) {
    LNode *oddHead = (LNode *)malloc(sizeof(LNode));  // 奇数链表的头结点
    LNode *evenHead = (LNode *)malloc(sizeof(LNode)); // 偶数链表的头结点
    LNode *oddTail = oddHead;   // 奇数链表的尾指针
    LNode *evenTail = evenHead; // 偶数链表的尾指针
    
    LNode *p = L->next;  // 遍历原链表
    while (p != NULL) {
        LNode *next = p->next;  // 保存后继
        if (p->data % 2 != 0) { // 奇数
            oddTail->next = p;
            oddTail = p;
        } else {                // 偶数
            evenTail->next = p;
            evenTail = p;
        }
        p = next;
    }
    
    oddTail->next = evenHead->next;  // 奇数链表尾部连接偶数链表头部
    evenTail->next = NULL;           // 偶数链表尾部置空
    L->next = oddHead->next;         // 原链表头结点连接奇数链表头部
    
    free(oddHead);   // 释放临时头结点
    free(evenHead);  // 释放临时头结点
}

复杂度分析：

• 时间复杂度O(n)：遍历一次链表
• 空间复杂度O(1)：只使用了几个辅助指针（临时头结点是常数空间）

评分标准：

• 算法思路正确（4分）
• 代码实现正确（4分）
• 复杂度分析正确（2分）

示例题4（选择题）

设有一个带头结点的单链表，头指针为L，以下（ ）操作序列可以实现"在第一个数据结点之前插入新结点s"。 A. s->next = L; L = s; B. s->next = L->next; L->next = s; C. s->next = L->next->next; L->next = s; D. L->next = s; s->next = L->next;

答案：B

解析：

“在第一个数据结点之前插入"等价于"在头结点之后插入”。

选项A：s->next = L; L = s;——修改了头指针L，且s指向原来的L，逻辑错误。 选项B：s->next = L->next; L->next = s;——先在s后面连上原来的第一个结点，再让头结点指向s。正确！这就是标准的"在头结点后面插入"操作。 选项C：跳过了第一个结点，在第二个结点之前插入。错误。 选项D：先让L->next = s，此时L->next已经是s了，再s->next = L->next就是s->next = s，自环。错误。

示例题5（简答题）

请解释为什么在单链表中，"在已知结点p之后插入"的时间复杂度是O(1)，而"在已知结点p之前插入"的时间复杂度是O(n)。如果要使"在p之前插入"也能在O(1)时间内完成，有什么方法？

参考答案：

（1）为什么后插O(1)、前插O(n)：

在单链表中，每个结点只存储了后继结点的指针（next），没有存储前驱结点的指针。

• 在p之后插入：只需要修改p的next域和新结点的next域，两个操作都是O(1)。
• 在p之前插入：需要找到p的前驱结点，但单链表没有前驱指针，只能从头指针开始逐个遍历，最坏情况需要遍历n-1个结点，时间复杂度O(n)。

（2）O(1)前插的方法：

"偷天换日"法：

1. 先在p之后插入新结点s（O(1)）
2. 交换p和s的数据域（O(1)）
3. 效果等价于在p之前插入了一个新结点

总时间复杂度O(1)。但缺点是修改了p的数据域，如果题目不允许修改其他结点的数据，则不能用此方法。

另一种方法是使用双链表（增加前驱指针），这样可以直接通过p的前驱指针找到前驱结点，前插也是O(1)。但这已经超出了单链表的范畴。

3.3 使用说明

如何使用命题Prompt：

1. 直接复制：将3.1节的Prompt模板复制到AI对话中
2. 调整参数：根据需要调整题目数量、难度、题型比例
3. 指定重点：可以指定AI重点考查某个知识点（如"多生成头插法相关的题目"）
4. 验证答案：AI生成的题目可能有错误，一定要自己验证答案的正确性
5. 组合使用：可以将多道题目组合成一套模拟卷，控制总时间和总分

注意事项：

• AI生成的题目质量参差不齐，建议与真题对照，确保难度和风格接近
• 对于算法设计题，要检查AI给出的代码是否有边界问题
• 可以将AI生成的题目与同学讨论，互相验证

模块4：AI讲题Prompt

4.1 讲题Prompt模板

你是一位耐心细致的408考研数据结构辅导老师。学生遇到了一道关于单链表的题目，请你详细讲解。

## 讲解要求

### 第一步：理解题意
- 用自己的话复述题目要求
- 标出题目中的关键信息（如"带头结点"、"O(1)时间"等）
- 明确题目考查的知识点

### 第二步：分析思路
- 从最基础的概念出发，逐步推导
- 解释为什么选择这种思路（而不是其他思路）
- 如果有多种解法，简要对比优劣

### 第三步：详细解答
- 一步步展示解题过程
- 对于代码题，逐行解释代码的含义和作用
- 对于选择题，分析每个选项为什么对/错

### 第四步：总结归纳
- 总结这道题考查的核心知识点
- 归纳同类题目的通用解题方法
- 指出容易出错的地方

### 第五步：拓展延伸
- 给出1-2道类似的练习题
- 指出这个知识点在真题中的其他考法

## 讲解风格
- 语言通俗易懂，避免过于学术化
- 用"我"的视角，像朋友一样讲解
- 适当使用类比和生活化的例子
- 重要结论要强调（用"注意"、"关键"等词）
- 代码要配合图示说明

## 输出格式
使用Markdown格式，代码用C语言，关键步骤用加粗标注

4.2 AI生成的讲解示例

题目：已知带头结点的单链表L，以下算法的功能是什么？

void Mystery(LinkList &L) {
    LNode *p = L->next;
    LNode *q;
    L->next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

讲解：

好的，我们一起来分析这段代码。

第一步：理解题意

题目给我们一段代码，让我们判断它的功能。代码中有几个关键信息：

• 带头结点的单链表
• 参数是LinkList &L（引用传递，说明会修改链表本身）
• 用到了while循环遍历

第二步：逐行分析

让我们一步步跟踪执行：

LNode *p = L->next;    // p指向第一个数据结点
LNode *q;
L->next = NULL;        // 关键！头结点的next置空，相当于"断开"了原链表

到这里，头结点变成了"孤立"的，它的next为NULL。而p指向原来的第一个数据结点。

while (p != NULL) {
    q = p->next;           // 保存p的后继
    p->next = L->next;     // 把p的next指向头结点的后继
    L->next = p;           // 头结点的next指向p
    p = q;                 // p前进到原来的后继
}

看这个循环体——p->next = L->next; L->next = p;——这不就是头插法吗？

每次把p指向的结点插入到头结点后面！

第三步：得出结论

这段代码的功能是：将单链表逆置。

原理：把原链表的每个结点依次"头插"到新的链表（以头结点为起点）中。因为头插法的特点是新元素总是插在最前面，所以最后建成的链表顺序和原链表相反——也就是逆置了。

图示辅助理解：

原链表：L → [1] → [2] → [3] → NULL

初始：L → NULL（断开）    p → [1] → [2] → [3] → NULL

第1轮：L → [1] → NULL     p → [2] → [3] → NULL
第2轮：L → [2] → [1] → NULL     p → [3] → NULL
第3轮：L → [3] → [2] → [1] → NULL     p → NULL

结束！链表逆置为 3 → 2 → 1

第四步：总结归纳

• 核心知识点：头插法的应用
• 通用方法：看到"L->next = NULL + while循环 + 头插"的模式，就是链表逆置
• 易错点：注意L->next = NULL这一步不能漏，否则原来的链表关系还在，就不是逆置而是复制了

第五步：拓展延伸

类似题目：

1. 给定单链表L，设计算法将其逆置，要求空间复杂度O(1)。（就是这道题的代码）
2. 给定单链表L，判断它是否为回文链表。（可以先逆置后半部分，再比较）

4.3 易错题记录

在使用AI讲题的过程中，我整理了以下容易出错的知识点：

易错题1：头插法的指针顺序

很多同学记住了"先连后断"，但在实际写代码时还是会搞反。建议用"新结点先和后面的连，再和前面的连"来记忆。

易错题2：头结点算不算"第1个"

头结点不算有效数据结点。按位查找时，第一个数据结点是第1位，不是第0位。但在插入操作中，头结点是第1个数据结点的"前驱"（位置0）。

易错题3：free之后还能访问吗？

不能！free之后，该内存可能被分配给其他变量，继续访问就是"未定义行为"。

模块5：AI错题复盘Prompt

5.1 错题复盘Prompt模板

你是一位善于分析错因的408考研数据结构辅导老师。学生做错了以下题目，请帮助他进行错题复盘。

## 复盘流程

### 第一步：还原做题过程
- 让学生描述当时的思路
- 找出是在哪一步开始偏离正确方向
- 确认是"不会"还是"会但做错了"

### 第二步：分析错因
从以下维度分析：
1. **知识性错误**：概念不清、定义记错
2. **逻辑性错误**：推理过程有误、因果关系搞反
3. **操作性错误**：指针顺序搞反、边界条件遗漏
4. **习惯性错误**：审题不清、计算粗心
5. **心理性错误**：紧张、想当然、时间不够

### 第三步：正确解法
- 给出完整的正确解法
- 对比学生的错误解法，标出关键差异
- 解释为什么正确解法是对的

### 第四步：举一反三
- 分析这类题目的通用解题方法
- 给出2-3道类似题目进行巩固练习
- 总结"防错口诀"或"检查清单"

### 第五步：追踪记录
- 记录错因分类
- 标记需要重点复习的知识点
- 设定复习时间（1天后、3天后、7天后）

## 输出格式
使用结构化的格式，清晰标出错因、正确解法、巩固练习

5.2 AI生成的复盘示例

错题：

题目：已知带头结点的单链表L，写出在第i个位置插入值为x的结点的算法。

我的错误代码：

bool ListInsert(LinkList &L, int i, ElemType x) {
    LNode *p = L->next;  // 错在这里
    int j = 1;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

复盘分析：

第一步：还原做题过程

学生的思路是：找到第i-1个结点，在它后面插入新结点。思路是对的，但查找的起点错了。

第二步：分析错因

知识性错误：学生把查找起点设为L->next（第一个数据结点），但应该设为L（头结点）。

原因分析：学生没有理解"头结点是第一个数据结点的前驱"这个关键事实。当i=1时，前驱是头结点（位置0），不是第一个数据结点（位置1）。

第三步：正确解法

bool ListInsert(LinkList &L, int i, ElemType x) {
    if (i < 1) return false;
    
    LNode *p = L;       // 修正：从头结点开始，不是L->next
    int j = 0;          // 修正：头结点是第0个位置
    
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL) return false;  // i超出范围
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

关键差异：

• 错误：p = L->next, j = 1（从第一个数据结点开始计数）
• 正确：p = L, j = 0（从头结点开始计数）

为什么：插入到第i个位置，需要找到第i-1个结点（前驱）。当i=1时，前驱是头结点（位置0）。如果从第一个数据结点开始（位置1），当i=1时，循环不执行，p指向第一个数据结点，在它后面插入就变成了在第2个位置插入——错位了。

第四步：举一反三

类似题目：

1. 删除第i个结点——同样需要找第i-1个结点，起点也应该是头结点
2. 交换第i个和第j个结点——需要分别找到它们的前驱

防错口诀：

“插入删除找前驱，头结点是第零个；从头开始j等于零，不会错位不会错。”

5.3 错题归因统计

根据我对同学们常见错误的统计，单链表部分的错题归因如下：

重点复习建议：

• 指针操作顺序：多画图，多写代码，形成肌肉记忆
• 查找起点：记住"插入删除找前驱，从头结点开始"
• 边界条件：养成"每个指针使用前先判空"的习惯

模块6：AI模拟卷Prompt

6.1 模拟卷Prompt模板

你是一位408考研数据结构命题专家。请根据以下要求，生成一套关于"单链表及其基本运算"的模拟卷。

## 试卷结构
- 总分：100分
- 时间：120分钟
- 题型分布：
  - 选择题：10题 × 3分 = 30分
  - 填空题：5题 × 4分 = 20分
  - 简答题：3题 × 6分 = 18分
  - 算法设计题：2题 × 16分 = 32分

## 知识点覆盖要求
- 结点结构（5-10%）
- 头结点与头指针（10-15%）
- 头插法与尾插法（15-20%）
- 查找操作（10-15%）
- 插入操作（15-20%）
- 删除操作（15-20%）
- 综合应用（10-15%）

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

## 出题要求
1. 选择题要有干扰性，选项不能太明显
2. 填空题考查关键代码或核心概念
3. 简答题需要用自己的话解释
4. 算法题参考408真题大题风格，要求完整代码+复杂度分析
5. 所有题目默认使用带头结点的单链表
6. 代码使用C语言

## 输出格式
- 先输出试卷（不含答案）
- 再输出参考答案和评分标准

6.2 AI生成的完整模拟卷

单链表及其基本运算 模拟卷

总分：100分 时间：120分钟

一、选择题（每题3分，共30分）

1. 单链表中，每个结点包含的指针域个数是（ ） A. 0 B. 1 C. 2 D. 不确定

2. 带头结点的单链表L为空的判定条件是（ ） A. L == NULL B. L->next == NULL C. L->next == L D. L != NULL

3. 在单链表中，在结点p之后插入结点s的操作是（ ） A. p->next = s; s->next = p->next; B. s->next = p->next; p->next = s; C. s->next = p; p->next = s; D. p->next = s->next; s->next = p;

4. 头插法建立单链表时，若输入序列为{1, 2, 3, 4, 5}，则建立的链表中元素顺序为（ ） A. {1, 2, 3, 4, 5} B. {5, 4, 3, 2, 1} C. {1, 5, 2, 4, 3} D. {5, 1, 4, 2, 3}

5. 在单链表中，按位查找第i个元素的时间复杂度为（ ） A. O(1) B. O(log₂n) C. O(n) D. O(n²)

6. 已知单链表中结点p的前驱结点为pre，在p之前插入结点s的操作是（ ） A. s->next = pre->next; pre->next = s; B. s->next = p; pre->next = s; C. pre->next = s; s->next = p; D. A和C都对

7. 以下代码段的功能是（ ）

while (p->next != NULL) {
    p = p->next;
}

A. 遍历链表 B. 找到最后一个结点 C. 删除最后一个结点 D. 求链表长度

8. 在单链表中删除结点p的直接后继结点，需要修改的指针个数为（ ） A. 0 B. 1 C. 2 D. 3

9. 尾插法建立单链表时，需要维护一个尾指针r，其主要目的是（ ） A. 方便遍历 B. 方便查找 C. 使每次插入的时间复杂度为O(1) D. 方便排序

10. 以下关于头结点的说法中，正确的是（ ） A. 头结点是链表的第一个数据结点 B. 头结点的数据域存储链表的长度 C. 头结点使得对第一个数据结点的操作和其他结点的操作统一 D. 单链表必须有头结点

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

11. 单链表的结点结构中，数据域用于存储______，指针域用于存储______。

12. 头插法建立单链表时，新结点总是插入到______之后，最终链表中元素的顺序与输入顺序______。

13. 在带头结点的单链表中，判断链表为空的条件是______。

14. 以下代码的功能是______：

LNode *p = L->next;
int count = 0;
while (p != NULL) {
    count++;
    p = p->next;
}

15. 在单链表中，已知结点p，要在p之后插入结点s，关键的两步操作是（用代码表示）： 第一步：______ 第二步：______

三、简答题（每题6分，共18分）

16. 简述头结点的作用（至少写出3点）。

17. 比较头插法和尾插法建立单链表的优缺点。

18. 为什么在单链表中"在已知结点p之后插入"是O(1)，而"在已知结点p之前插入"是O(n)？有什么方法可以使前插也达到O(1)？

四、算法设计题（每题16分，共32分）

19. 已知带头结点的单链表L，设计算法删除链表中所有值等于x的结点，并释放其空间。要求： （1）写出完整的C语言代码 （2）分析时间复杂度和空间复杂度 （3）说明你的算法思路

20. 已知带头结点的单链表L，设计算法找出链表中倒数第k个结点的值。要求： （1）写出完整的C语言代码 （2）分析时间复杂度和空间复杂度 （3）你的算法应该只遍历链表一次

参考答案与评分标准

一、选择题

1. B（单链表每个结点有1个next指针）
2. B（头结点的next为空表示空表）
3. B（先连后断：s先连p的后继，p再连s）
4. B（头插法逆序）
5. C（需要从头遍历到第i个位置）
6. D（A和C等价，都是正确的在p之前插入的操作）
7. B（循环结束时p指向最后一个结点）
8. B（只需修改p的next域：p->next = p->next->next）
9. C（有尾指针就不需要遍历到尾部）
10. C（头结点的核心作用是统一操作逻辑）

二、填空题

1. 数据元素（或实际数据）；后继结点的地址（或后继结点的指针）
2. 头结点；相反
3. L->next == NULL
4. 求单链表的长度（不含头结点）
5. 第一步：s->next = p->next；第二步：p->next = s

三、简答题

16. 头结点的作用：

1. 统一操作逻辑：使得对第一个数据结点的插入删除和其他位置的操作一致，不需要特殊处理
2. 方便空表处理：空表时头指针指向头结点（不为NULL），判空条件统一为L->next == NULL
3. 标识链表：头结点的存在使得所有数据结点都有前驱，简化边界条件

17. 头插法：

• 优点：代码简洁，不需要维护尾指针
• 缺点：元素顺序与输入顺序相反
• 适用：逆序建表、链栈

尾插法：

• 优点：元素顺序与输入顺序一致
• 缺点：需要维护尾指针，代码稍复杂，最后需要r->next = NULL
• 适用：正序建表、队列的链式实现

18.

• 后插O(1)：只需修改p的next和新结点的next，两步操作
• 前插O(n)：需要找p的前驱，单链表没有前驱指针，只能从头遍历
• O(1)前插方法：先在p后面插入，再交换p和新结点的数据域（"偷天换日"法）

四、算法设计题

19. 删除所有值为x的结点：

void DeleteAllX(LinkList &L, ElemType x) {
    LNode *p = L;          // p指向待删结点的前驱
    LNode *q;
    
    while (p->next != NULL) {
        if (p->next->data == x) {
            q = p->next;           // q指向要删除的结点
            p->next = q->next;     // 断开q
            free(q);               // 释放q
            // p不移动，因为新的p->next可能还是x
        } else {
            p = p->next;           // 不是x，p后移
        }
    }
}

时间复杂度O(n)，空间复杂度O(1)。

评分标准：代码正确10分，复杂度分析4分，思路说明2分。

20. 倒数第k个结点（快慢指针法）：

ElemType FindKthFromEnd(LinkList L, int k, bool &found) {
    LNode *fast = L->next;  // 快指针
    LNode *slow = L->next;  // 慢指针
    
    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            found = false;  // k超出链表长度
            return -1;
        }
        fast = fast->next;
    }
    
    // 快慢指针同时走，快指针到末尾时，慢指针就是倒数第k个
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    found = true;
    return slow->data;
}

时间复杂度O(n)（只遍历一次），空间复杂度O(1)。

评分标准：代码正确10分，复杂度分析4分，思路说明2分。

6.3 评分标准参考

总体评分原则：

• 选择题：选对给满分，选错不给分
• 填空题：关键词正确即可给分
• 简答题：要点齐全给满分，表述不清酌情扣分
• 算法题：
  • 思路正确（30%）
  • 代码实现（40%）
  • 复杂度分析（20%）
  • 代码规范（10%）

代码规范评分细则：

• 变量命名有意义（2分）
• 指针使用前判空（2分）
• 边界条件处理正确（2分）
• 有必要的注释（2分）
• 代码结构清晰（2分）

模块7：延伸阅读

7.1 教材参考

核心教材：

1. 王道考研《数据结构考研复习指导》
   • 第2章 线性表（单链表部分）
   • 特点：紧贴408真题，代码规范，解析详细
   • 建议：至少刷3遍，第一遍理解，第二遍手写代码，第三遍限时做题
2. 严蔚敏《数据结构（C语言版）》
   • 第2章 线性表（链式表示部分）
   • 特点：理论严谨，定义规范，是408命题的主要参考
   • 建议：重点看链表的基本操作和算法分析
3. 王道考研《数据结构考研复习指导（历年真题解析）》
   • 所有涉及单链表的真题及详解
   • 建议：按年份做一遍，标注错题

辅助教材：

1. 《大话数据结构》——程杰
   • 第4章 线性表的链式存储
   • 特点：语言通俗，图示丰富，适合入门
   • 建议：如果看王道书觉得吃力，可以先看这本打基础
2. 《数据结构与算法分析——C语言描述》——Mark Allen Weiss
   • 第3章 表、栈和队列
   • 特点：英文经典教材，代码质量高
   • 建议：学有余力时阅读，对理解链表的高级应用有帮助

7.2 视频课程

推荐视频：

1. 王道考研数据结构视频课
   • 平台：B站
   • 内容：线性表-链式存储部分
   • 特点：紧贴考纲，讲解清晰，配套王道书使用效果最佳
   • 建议时长：2-3小时
2. 青岛大学王卓老师数据结构视频
   • 平台：B站
   • 内容：单链表的基本操作
   • 特点：讲解细致，代码演示完整，适合零基础
   • 建议时长：3-4小时
3. 浙大数据结构视频（陈越、何钦铭）
   • 平台：中国大学MOOC
   • 内容：线性结构-链表部分
   • 特点：学术性强，对理解链表本质有帮助
   • 建议时长：2-3小时

学习建议：

• 先看一个视频课理解概念
• 然后对照教材手写代码
• 最后做真题检验掌握程度

7.3 知识关联图

知识关联说明：

• 单链表 → 双链表：双链表在每个结点中增加一个前驱指针（prior），使得前插操作也能O(1)完成
• 单链表 → 循环链表：将单链表最后一个结点的next指向头结点（或头结点的next），形成环
• 单链表 → 静态链表：用数组模拟链表，适用于不支持指针的语言
• 单链表 → 顺序表：两者是线性表的两种存储方式，各有优劣，可以互相转换

模块8：Checklist

8.1 知识点清单

完成本节学习后，你应该能够：

概念理解：

• 能准确描述单链表的结点结构（data域 + next域）
• 能区分头结点和头指针，说出各自的作用
• 能说出单链表相比顺序表的优缺点（至少各3点）
• 能解释为什么头结点能让操作逻辑统一
• 能画出带头结点和不带头结点的单链表结构图

代码实现：

• 能独立写出初始化代码（创建头结点）
• 能独立写出头插法建表代码（指针顺序正确）
• 能独立写出尾插法建表代码（含尾指针维护和最后置空）
• 能独立写出按位查找代码（区分查找起点）
• 能独立写出按值查找代码
• 能独立写出后插操作代码（先连后断）
• 能独立写出前插操作代码（找前驱 + 后插）
• 能独立写出按位删除代码（找前驱 + 断开 + 释放）
• 能独立写出按值删除代码
• 能独立写出遍历和求长度代码

复杂度分析：

• 能说出每个操作的时间复杂度和空间复杂度
• 能解释为什么前插是O(n)而后插是O(1)
• 能分析头插法和尾插法建表的时间复杂度

真题能力：

• 能正确判断指针操作序列的正确性
• 能区分带头结点和不带头结点链表的代码差异
• 能设计完整的链表操作算法（含边界处理和复杂度分析）
• 能识别并纠正常见的代码错误（指针丢失、空指针等）

8.2 自测问题

完成学习后，尝试回答以下问题（不看答案）：

基础题：

1. 单链表的结点由哪两部分组成？各自的作用是什么？
2. 头指针和头结点有什么区别？
3. 带头结点的单链表，空表的判定条件是什么？
4. 头插法和尾插法建立的链表，元素顺序有什么不同？
5. 在结点p后面插入新结点s，代码怎么写？指针顺序能反吗？

进阶题： 6. 为什么"在p之前插入"需要O(n)？有什么O(1)的方法？ 7. 删除结点p的后继结点，需要修改几个指针？ 8. 尾插法建表时，为什么最后要r->next = NULL？ 9. 不带头结点的单链表，插入到第1个位置需要特殊处理吗？ 10. 如何只遍历一次链表就找到倒数第k个结点？

综合题： 11. 设计算法：将两个有序单链表合并为一个有序单链表。 12. 设计算法：判断单链表是否有环。 13. 设计算法：找到单链表的中间结点（只遍历一次）。

8.3 完成度评估

根据自测结果，评估自己的掌握程度：

A级（完全掌握）：

• 所有基础题和进阶题都能正确回答
• 综合题能独立写出完整代码
• 能做对历年真题中的链表题
• 建议：可以进入下一篇（双链表与循环链表）的学习

B级（基本掌握）：

• 基础题全部正确，进阶题大部分正确
• 综合题能写出思路但代码有小错误
• 真题选择题正确率80%以上
• 建议：重点复习错题对应的知识点，再手写一遍代码

C级（需要加强）：

• 基础题有错误，进阶题困难
• 代码写不出来或错误很多
• 真题选择题正确率60%以下
• 建议：重新看视频课和教材，从零开始手写每个操作的代码，至少写3遍

D级（需要重学）：

• 基础概念混淆（如分不清头结点和头指针）
• 完全写不出代码
• 建议：先看《大话数据结构》入门，再看王道书，配合视频课学习

写在最后：单链表是数据结构的"基本功"，就像武术里的扎马步——看着简单，但要扎得稳需要反复练习。我的建议是：不要只看懂，一定要手写代码。在纸上写、在电脑上敲、对着真题写——至少把初始化、头插、尾插、查找、插入、删除这6个操作各写3遍。写到手不用想就能写出正确的指针顺序，你就真正掌握了。 下一篇我们将学习双链表和循环链表，它们都是在单链表基础上的扩展。把单链表学扎实，后面的内容会轻松很多。加油！

参考资料：

1. 王道考研. 数据结构考研复习指导[M]. 北京: 电子工业出版社.
2. 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京: 清华大学出版社.
3. 程杰. 大话数据结构[M]. 北京: 清华大学出版社.

在这里插入图片描述