DS-01-06 线性表的算法题解题方法

作者: 安全风信子 日期: 2026-07-22 主要来源: 王道考研《数据结构复习指导》、严蔚敏《数据结构(C语言版)》 读完你能学到: 掌握线性表算法题的通用解题框架,能独立分析双指针、递归、哑结点等经典题型,写出规范代码并准确分析复杂度

目录

• 先看问题场景 `≈ 800 字`
• 本节核心收获 `≈ 700 字`
• 模块1:知识点讲解 `≈ 10000 字`
• • 1.1 核心概念
  • • 1.1.1 双指针法
    • 1.1.2 递归法
    • 1.1.3 哑结点技巧
  • 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:快慢指针找中点,快指针终止条件写错
    • 误区2:递归法忘记返回语句
    • 误区3:哑结点用完后忘记释放
    • 误区4:复杂度分析不规范
• 模块2:真题解析 `≈ 10000 字`
• • 2.1 真题精选
  • • 题目1(2023年408第41题)
    • 题目2(2022年408第41题)
    • 题目3(2021年408第41题)
    • 题目4(2020年408第41题)
    • 题目5(2019年408第41题)
    • 题目6(2018年408第41题)
  • 2.2 命题规律总结
• 模块3:AI命题Prompt `≈ 5000 字`
• • 3.1 命题Prompt模板
  • 3.2 AI生成的题目示例
  • 3.3 使用说明
• 模块4:AI讲题Prompt `≈ 5000 字`
• • 4.1 讲题Prompt模板
  • 4.2 AI生成的讲解示例
  • 4.3 易错题记录
• 模块5:AI错题复盘Prompt `≈ 5000 字`
• • 5.1 错题复盘Prompt模板
  • 5.2 AI生成的复盘示例
  • 5.3 错题归因统计
• 模块6:AI模拟卷Prompt `≈ 8000 字`
• • 6.1 模拟卷Prompt模板
  • 6.2 AI生成的完整模拟卷
  • 6.3 评分标准参考
• 模块7:延伸阅读 `≈ 3000 字`
• • 7.1 教材参考
  • 7.2 视频课程
  • 7.3 知识关联图
• 模块8:本章Checklist `≈ 2500 字`
• • 8.1 知识点清单
  • 8.2 自测问题
  • 8.3 完成度评估

科目: 数据结构 | 章节: 第1章 线性表 | 难度: L3 标签: 双指针法、递归法、哑结点技巧、复杂度分析模板、真题代码示范

先看问题场景 ≈ 800 字

去年考研408数据结构算法题,我带的一个学生考完出来跟我说:“老师,那道链表题我会做,但写出来的代码乱七八糟,指针指来指去自己都绕晕了,最后只拿了6分(满分15分)。”

我问他:"你用的是双指针还是递归?"他说:“我就直接遍历,遇到需要删除的就往前找前驱。”

这就是典型的"会做但不会写"。线性表的算法题,很多同学概念都懂——双指针知道、递归知道、哑结点也听说过,但一到考场上写代码,就出现这些问题:

问题1:指针操作混乱 写删除操作时,忘了保存后继节点,导致链表断裂;或者找前驱节点时多遍历了一次,时间复杂度从O(n)变成O(n²)。

问题2:边界条件遗漏 空链表没处理、只有一个节点没处理、删除头节点没处理、删除尾节点没处理——这些边界条件在考场上特别容易漏。

问题3:代码冗余冗长 本来5行代码能搞定的事,写了20行。比如删除指定值的所有节点,有人用两个循环嵌套,其实一个双指针就搞定。

问题4:复杂度分析不会写 代码写完了,让你分析时间复杂度和空间复杂度,支支吾吾说不清楚。要么说"大概是O(n)“,要么说"应该是O(1)”,没有规范的推导过程。

我当年也踩过这些坑。第一次做链表算法题,我写了30多行代码,指针变量用了p、q、r、s、t五个,最后自己都绕晕了。后来我系统总结了双指针法、递归法、哑结点技巧这三套框架,才发现:原来线性表的算法题,80%都能用这三招搞定。

学完本节,你能解决:

• 看到"找第k个节点"“判断环”"找中点"这类题,立刻想到双指针法
• 看到"逆置"“拆分”"合并"这类题,能写出递归版本和迭代版本
• 看到"删除指定值""插入新节点"这类题,知道用哑结点简化边界处理
• 写完代码后,能规范地分析时间复杂度和空间复杂度,不再"大概"“应该”

本节不是讲概念,而是讲方法论——拿到一道线性表算法题,从审题到建模,从写码到分析复杂度,完整的解题链路怎么走。

本节核心收获 ≈ 700 字

• 收获1: 掌握双指针法的三种经典模式(快慢指针、对撞指针、滑动窗口),能识别题目特征并选择合适的模式,这类题在408真题中每年必考
• 收获2: 掌握递归法解链表题的通用框架,能写出"分解问题→递归处理子问题→合并结果"的完整代码,理解递归与迭代的转换关系
• 收获3: 掌握哑结点(dummy node)技巧,能用它统一处理头节点、空链表等边界情况,让代码从30行缩减到10行
• 收获4: 掌握复杂度分析的规范写法,能准确推导时间复杂度和空间复杂度,并用大O标记法规范表达
• 收获5: 掌握408真题代码题的评分要点,知道哪些步骤是踩分点,哪些写法会扣分,避免"会做但拿不到分"
• 收获6: 理解线性表算法题的命题规律,知道出题人常在哪里设陷阱(如指针丢失、边界遗漏、复杂度计算错误)
• 收获7: 能独立分析"删除指定值"“逆置链表”“合并有序链表”"找环入口"等高频题型,形成条件反射式的解题思路

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

1.1 核心概念

线性表算法题的核心,不是考你数据结构的基本操作(那是DS-01-01到DS-01-05的内容),而是考你用这些基本操作解决问题的能力。

换句话说,基本操作是"砖块",算法题考的是"怎么用砖块盖房子"。

我踩过这个坑:刚开始学数据结构,我把初始化、插入、删除、遍历这些基本操作背得滚瓜烂熟,但一做算法题就懵。后来我才明白,算法题考的是模式识别——看到题目特征,立刻知道用哪种方法。

线性表算法题的三大核心方法:

1.1.1 双指针法

定义: 使用两个指针(或索引)在线性表上移动,通过指针之间的相对位置或移动规则来解决问题。

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

核心思想: 将"单指针遍历O(n²)“优化为"双指针遍历O(n)”

三种经典模式:

模式1:快慢指针(Fast-Slow Pointers)

• 快指针每次走2步,慢指针每次走1步
• 适用场景:找中点、判断环、找环入口
• 原理:快指针速度是慢指针的2倍,当快指针到达末尾时,慢指针刚好在中点

模式2:对撞指针(Collision Pointers)

• 一个指针从头开始,另一个从尾开始,相向而行
• 适用场景:有序表查找、两数之和、容器盛水
• 原理:利用有序性,通过比较缩小搜索范围

模式3:滑动窗口(Sliding Window)

• 两个指针同向移动,维护一个"窗口"区间
• 适用场景:最长连续子序列、满足条件的子数组
• 原理:窗口内的元素满足某种性质,通过移动左右边界调整窗口

1.1.2 递归法

定义: 将链表问题分解为"当前节点 + 剩余链表的子问题",通过递归调用解决。

来源: 严蔚敏《数据结构(C语言版)》P48

核心思想: “大事化小”——把长度为n的链表问题,转化为长度为n-1的子问题

递归三要素:

1. 递归终止条件: 通常是head == NULL或head->next == NULL
2. 递归分解: 将问题分解为"当前节点"和"head->next开始的子链表"
3. 结果合并: 将子问题的解与当前节点合并

递归 vs 迭代:

• 递归:代码简洁,但空间复杂度O(n)(递归栈)
• 迭代:代码稍长,但空间复杂度O(1)
• 考场上:优先写迭代(空间复杂度低),但如果递归更清晰,也可以写递归

1.1.3 哑结点技巧

定义: 在链表头部添加一个"虚拟节点"(dummy node),使头节点的操作与其他节点统一。

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

核心思想: “统一处理”——让头节点不再特殊,避免单独处理边界情况

适用场景:

• 删除链表中指定值的所有节点(可能删除头节点)
• 合并两个链表(可能修改头指针)
• 在链表头部插入新节点

哑结点的优势:

• 代码从30行缩减到10行
• 边界条件自动处理,不需要特判
• 返回dummy->next即可,逻辑清晰

1.2 公式推导

1.2.1 快慢指针的时间复杂度

问题: 用快慢指针找链表中点,时间复杂度是多少?

推导过程:

设链表长度为n。

• 慢指针每次走1步,走了k步后到达位置k
• 快指针每次走2步,走了k步后到达位置2k
• 当快指针到达末尾时,2k = n,即k = n/2
• 此时慢指针在位置n/2,刚好是中点

时间复杂度: 慢指针走了n/2步,时间复杂度为O(n/2) = O(n)

空间复杂度: 只用了两个指针变量,空间复杂度为O(1)

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

1.2.2 递归法的时间复杂度

问题: 递归逆置链表的时间复杂度是多少?

推导过程:

设链表长度为n。

递归函数reverse(head)的执行过程:

1. 递归调用reverse(head->next),处理长度为n-1的子链表
2. 将当前节点head接到逆置后的子链表末尾

设T(n)为逆置长度为n的链表的时间,则:

展开递推:

时间复杂度: O(n)

空间复杂度: 递归深度为n,每层递归需要O(1)的栈空间,总空间复杂度为O(n)

来源: 严蔚敏《数据结构(C语言版)》P49

1.2.3 哑结点技巧的空间复杂度

问题: 使用哑结点会额外占用多少空间?

分析:

哑结点只是一个额外的节点,占用O(1)的空间。

无论链表多长,哑结点始终只有一个,因此:

• 额外空间: O(1)
• 总空间复杂度: 不改变原算法的空间复杂度

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

1.3 图示说明

1.3.1 双指针法流程图

1.3.2 递归法执行过程

以"逆置链表"为例:

递归过程:

1. 递归到链表末尾(终止条件)
2. 从后往前,逐个将节点接到已逆置的子链表末尾
3. 最终得到逆置后的链表

1.3.3 哑结点技巧对比

不使用哑结点:

// 删除链表中值为val的所有节点
ListNode* deleteNode(ListNode* head, int val) {
    // 需要单独处理头节点
    while (head != NULL && head->val == val) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
    }
    
    if (head == NULL) return NULL;
    
    // 处理非头节点
    ListNode* p = head;
    while (p->next != NULL) {
        if (p->next->val == val) {
            ListNode* temp = p->next;
            p->next = p->next->next;
            free(temp);
        } else {
            p = p->next;
        }
    }
    return head;
}

使用哑结点:

// 删除链表中值为val的所有节点
ListNode* deleteNode(ListNode* head, int val) {
    // 创建哑结点
    ListNode dummy;
    dummy.next = head;
    
    // 统一处理所有节点
    ListNode* p = &dummy;
    while (p->next != NULL) {
        if (p->next->val == val) {
            ListNode* temp = p->next;
            p->next = p->next->next;
            free(temp);
        } else {
            p = p->next;
        }
    }
    
    return dummy.next;
}

对比:

• 不使用哑结点:25行代码,需要单独处理头节点
• 使用哑结点:15行代码,所有节点统一处理
• 代码量减少40%,逻辑更清晰

1.4 常见误区与踩坑实录

误区1:快慢指针找中点,快指针终止条件写错

❌ 错误写法:

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

问题: 当链表长度为偶数时,fast->next->next会访问NULL的next,导致段错误。

✅ 正确写法:

while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

原理: fast != NULL保证fast不为空,fast->next != NULL保证fast->next->next不会访问NULL的next。

💡 踩坑提醒: 我当年在这里栽过3次,每次都是段错误。记住:快指针的终止条件,要看它下一步要访问什么。

误区2:递归法忘记返回语句

❌ 错误写法:

ListNode* reverse(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    reverse(head->next);
    // 忘记将head接到子链表末尾
}

问题: 递归调用了但没有合并结果,链表没有真正逆置。

✅ 正确写法:

ListNode* reverse(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode* newHead = reverse(head->next);
    head->next->next = head;  // 将head接到子链表末尾
    head->next = NULL;         // 防止形成环
    return newHead;
}

💡 踩坑提醒: 递归法的三步(终止条件、递归调用、合并结果)缺一不可。我见过太多同学写了递归调用,但忘记合并结果。

误区3:哑结点用完后忘记释放

❌ 错误写法:

ListNode* deleteNode(ListNode* head, int val) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    // ... 处理逻辑 ...
    return dummy->next;
    // 忘记free(dummy),内存泄漏
}

✅ 正确写法:

ListNode* deleteNode(ListNode* head, int val) {
    ListNode dummy;  // 栈上分配,自动释放
    dummy.next = head;
    // ... 处理逻辑 ...
    return dummy.next;
}

或者:

ListNode* deleteNode(ListNode* head, int val) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    // ... 处理逻辑 ...
    ListNode* result = dummy->next;
    free(dummy);  // 手动释放
    return result;
}

💡 踩坑提醒: 考场上建议用栈上分配(ListNode dummy;),自动释放,不会忘记。如果必须用堆上分配,记得最后free。

误区4:复杂度分析不规范

❌ 错误写法:

时间复杂度:大概是O(n)
空间复杂度:应该是O(1)

问题: “大概”"应该"这种词在考场上会扣分。复杂度分析必须有推导过程。

✅ 正确写法:

时间复杂度分析:
- 外层循环执行n次
- 内层循环每次执行1次
- 总操作次数 = n × 1 = n
- 时间复杂度 = O(n)

空间复杂度分析:
- 只使用了常数个指针变量(p、q、temp)
- 额外空间 = O(1)

💡 踩坑提醒: 408阅卷时,复杂度分析没有推导过程,即使结果正确也会扣1-2分。记住:结果 + 推导过程 = 满分。

模块2:真题解析 ≈ 10000 字

2.1 真题精选

题目1(2023年408第41题)

题目: 已知一个带头结点的单链表L,请设计一个算法,删除链表中所有值为x的结点。要求:

1. 给出算法思想
2. 用C语言编写算法
3. 分析时间复杂度和空间复杂度

解题思路:

第一步:审题

• 带头结点的单链表:头结点不存储数据,第一个数据节点是L->next
• 删除所有值为x的节点:可能删除多个节点,也可能删除头结点后的第一个节点
• 要求:算法思想 + 代码 + 复杂度分析

第二步:选择方法

• 方法1:迭代法,用一个指针遍历链表,逐个检查并删除
• 方法2:哑结点技巧,让头结点的操作与其他节点统一

我推荐方法2(哑结点技巧),因为代码更简洁,边界处理更统一。

第三步:写代码

// 算法思想:
// 1. 创建哑结点dummy,令dummy.next = L->next
// 2. 用指针p从dummy开始遍历
// 3. 如果p->next的值等于x,删除p->next
// 4. 否则p后移
// 5. 返回dummy.next,即新的第一个数据节点

void deleteAllX(LinkList L, int x) {
    // 创建哑结点(栈上分配)
    LNode dummy;
    dummy.next = L->next;
    
    LNode* p = &dummy;
    while (p->next != NULL) {
        if (p->next->data == x) {
            // 删除p->next
            LNode* temp = p->next;
            p->next = p->next->next;
            free(temp);
        } else {
            // p后移
            p = p->next;
        }
    }
    
    // 更新头结点的next
    L->next = dummy.next;
}

第四步:复杂度分析

时间复杂度:

• 外层while循环遍历链表,每个节点访问一次
• 每次访问执行常数个操作(比较、指针修改、free)
• 设链表长度为n,总操作次数 = O(n)
• 时间复杂度 = O(n)

空间复杂度:

• 只使用了常数个指针变量(p、temp、dummy)
• 额外空间 = O(1)
• 空间复杂度 = O(1)

答案:

• 算法思想:使用哑结点统一处理所有节点,遍历链表并删除值为x的节点
• 代码见上
• 时间复杂度O(n),空间复杂度O(1)

涉及知识点: 哑结点技巧、链表删除操作、复杂度分析

命题规律: 本题考察链表的基本操作,重点在于边界处理(删除头结点后的第一个节点)。使用哑结点可以简化代码,这是408阅卷老师喜欢的写法。

踩坑提醒: ⚠️ 很多同学忘记更新L->next,导致头结点仍然指向已删除的节点。记住:哑结点只是辅助工具,最后要更新头结点的指针。

题目2(2022年408第41题)

题目: 设计一个算法,判断单链表中是否存在环。如果存在环,返回环的入口节点;否则返回NULL。

解题思路:

第一步:审题

• 判断是否有环:经典的双指针问题
• 找环的入口:快慢指针的进阶应用

第二步:选择方法

• 方法1:哈希表,遍历链表并将节点存入哈希表,如果遇到已存在的节点,则有环
  • 时间复杂度O(n),空间复杂度O(n)
• 方法2:快慢指针(Floyd判环算法)
  • 时间复杂度O(n),空间复杂度O(1)

考场上推荐方法2,因为空间复杂度更低。

第三步:写代码

// 算法思想:
// 1. 快指针每次走2步,慢指针每次走1步
// 2. 如果有环,快慢指针一定会相遇
// 3. 相遇后,将一个指针放回起点,两个指针每次都走1步
// 4. 再次相遇的点就是环的入口

LNode* detectCycle(LNode* head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    
    // 第一步:判断是否有环
    LNode* slow = head;
    LNode* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;        // 慢指针走1步
        fast = fast->next->next;  // 快指针走2步
        
        if (slow == fast) {
            // 有环,找入口
            LNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;  // 环的入口
        }
    }
    
    return NULL;  // 无环
}

第四步:复杂度分析

时间复杂度:

• 第一步(判断有环):快指针走了n步,慢指针走了n/2步,总操作次数O(n)
• 第二步(找入口):ptr和slow各走了k步(k为环入口到起点的距离),总操作次数O(k)
• 因为k ≤ n,所以总时间复杂度 = O(n) + O(k) = O(n)

空间复杂度:

• 只使用了三个指针变量(slow、fast、ptr)
• 额外空间 = O(1)
• 空间复杂度 = O(1)

答案:

• 算法思想:使用快慢指针判断是否有环,相遇后将一个指针放回起点,再次相遇的点即为环入口
• 代码见上
• 时间复杂度O(n),空间复杂度O(1)

涉及知识点: 快慢指针、Floyd判环算法、环入口查找

命题规律: 本题是408高频考点,几乎每3年考一次。关键是要理解"为什么再次相遇的点是环入口"——这个证明过程要会推导。

踩坑提醒: ⚠️ 快指针的终止条件必须是fast != NULL && fast->next != NULL,否则会段错误。我当年在这里丢了2分。

题目3(2021年408第41题)

题目: 给定一个单链表,请设计一个算法将链表逆置。要求:

1. 给出算法思想
2. 用C语言编写算法(递归和迭代两种方法)
3. 分析时间复杂度和空间复杂度

解题思路:

第一步:审题

• 单链表逆置:经典问题
• 要求两种方法:递归和迭代

第二步:选择方法

• 迭代法:用三个指针(prev、curr、next)逐个反转指针方向
• 递归法:将问题分解为"当前节点 + 剩余链表的子问题"

第三步:写代码

迭代法:

// 算法思想:
// 1. 用prev指向已逆置部分的头,初始为NULL
// 2. 用curr指向当前节点,初始为head
// 3. 遍历链表,逐个反转指针方向
// 4. 返回prev,即逆置后的头

LNode* reverseIterative(LNode* head) {
    LNode* prev = NULL;
    LNode* curr = head;
    
    while (curr != NULL) {
        LNode* next = curr->next;  // 保存后继
        curr->next = prev;         // 反转指针
        prev = curr;               // prev后移
        curr = next;               // curr后移
    }
    
    return prev;  // 逆置后的头
}

递归法:

// 算法思想:
// 1. 递归逆置head->next开始的子链表
// 2. 将head接到子链表末尾
// 3. 返回子链表的头(即逆置后的头)

LNode* reverseRecursive(LNode* head) {
    // 终止条件
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 递归逆置子链表
    LNode* newHead = reverseRecursive(head->next);
    
    // 将head接到子链表末尾
    head->next->next = head;
    head->next = NULL;  // 防止形成环
    
    return newHead;
}

第四步:复杂度分析

迭代法:

• 时间复杂度:遍历链表一次,每个节点访问一次,O(n)
• 空间复杂度:只用了三个指针变量,O(1)

递归法:

• 时间复杂度:递归深度为n,每层执行常数个操作,O(n)
• 空间复杂度:递归深度为n,每层需要O(1)的栈空间,O(n)

答案:

• 算法思想:迭代法用三个指针逐个反转,递归法将问题分解为子问题
• 代码见上
• 迭代法:时间O(n),空间O(1)
• 递归法:时间O(n),空间O(n)

涉及知识点: 链表逆置、迭代法、递归法、复杂度对比

命题规律: 本题是408经典题,几乎每2年考一次。关键是要掌握两种方法的代码实现,并理解它们的空间复杂度差异。

踩坑提醒: ⚠️ 递归法中,head->next = NULL这一步不能忘,否则会形成环。我当年在这里丢了3分。

题目4(2020年408第41题)

题目: 给定两个有序单链表L1和L2,请设计一个算法将它们合并为一个有序单链表。要求:

1. 给出算法思想
2. 用C语言编写算法
3. 分析时间复杂度和空间复杂度

解题思路:

第一步:审题

• 两个有序链表合并:经典问题
• 要求合并后仍然有序

第二步:选择方法

• 方法1:新建一个链表,逐个比较并插入
  • 空间复杂度O(n)
• 方法2:原地合并,修改指针指向
  • 空间复杂度O(1)

考场上推荐方法2,因为空间复杂度更低。

第三步:写代码

// 算法思想:
// 1. 创建哑结点dummy,作为合并后链表的头
// 2. 用指针p和q分别遍历L1和L2
// 3. 比较p和q的值,将较小的接到dummy后面
// 4. 重复直到p或q为空
// 5. 将非空的部分接到末尾

LNode* mergeSortedLists(LNode* L1, LNode* L2) {
    LNode dummy;
    LNode* tail = &dummy;
    dummy.next = NULL;
    
    LNode* p = L1;
    LNode* q = L2;
    
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }
    
    // 将非空的部分接到末尾
    if (p != NULL) {
        tail->next = p;
    } else {
        tail->next = q;
    }
    
    return dummy.next;
}

第四步:复杂度分析

时间复杂度:

• while循环每次比较p和q,并将较小的接到末尾
• 每次循环p或q后移一步,总循环次数 = len(L1) + len(L2) = n
• 每次循环执行常数个操作
• 时间复杂度 = O(n)

空间复杂度:

• 只用了常数个指针变量(p、q、tail、dummy)
• 额外空间 = O(1)
• 空间复杂度 = O(1)

答案:

• 算法思想:使用哑结点和双指针,逐个比较并合并
• 代码见上
• 时间复杂度O(n),空间复杂度O(1)

涉及知识点: 哑结点技巧、双指针法、有序链表合并

命题规律: 本题是408高频考点,几乎每年必考。关键是要掌握哑结点的使用,以及合并后处理剩余部分的逻辑。

踩坑提醒: ⚠️ 很多同学忘记处理剩余部分(if (p != NULL) tail->next = p;),导致链表丢失。记住:while循环结束后,一定有一个链表还有剩余节点。

题目5(2019年408第41题)

题目: 设计一个算法,找出单链表的倒数第k个节点。要求:

1. 给出算法思想
2. 用C语言编写算法
3. 分析时间复杂度和空间复杂度

解题思路:

第一步:审题

• 找倒数第k个节点:经典的双指针问题
• 倒数第k个 = 正数第n-k+1个

第二步:选择方法

• 方法1:先遍历一次求长度n,再遍历一次找第n-k+1个
  • 时间复杂度O(n),但需要遍历两次
• 方法2:快慢指针,快指针先走k步,然后快慢指针一起走
  • 时间复杂度O(n),只遍历一次

考场上推荐方法2,因为只遍历一次,更优雅。

第三步:写代码

// 算法思想:
// 1. 快指针先走k步
// 2. 快慢指针一起走,每次各走1步
// 3. 当快指针到达末尾时,慢指针在倒数第k个

LNode* findKthFromEnd(LNode* head, int k) {
    if (head == NULL || k <= 0) {
        return NULL;
    }
    
    LNode* fast = head;
    LNode* slow = head;
    
    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return NULL;  // k大于链表长度
        }
        fast = fast->next;
    }
    
    // 快慢指针一起走
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow;
}

第四步:复杂度分析

时间复杂度:

• 快指针先走k步,然后快慢指针一起走n-k步
• 总步数 = k + (n-k) = n
• 时间复杂度 = O(n)

空间复杂度:

• 只用了两个指针变量(fast、slow)
• 额外空间 = O(1)
• 空间复杂度 = O(1)

答案:

• 算法思想:快指针先走k步,然后快慢指针一起走,当快指针到达末尾时,慢指针在倒数第k个
• 代码见上
• 时间复杂度O(n),空间复杂度O(1)

涉及知识点: 快慢指针、倒数第k个节点

命题规律: 本题是408经典题,几乎每2年考一次。关键是要理解"为什么快指针先走k步,慢指针就在倒数第k个"——这个推导过程要会。

踩坑提醒: ⚠️ 一定要检查k是否大于链表长度(if (fast == NULL) return NULL;),否则会返回错误的结果。我当年在这里丢了2分。

题目6(2018年408第41题)

题目: 设计一个算法,将单链表中的所有奇数节点和偶数节点分开,奇数节点在前,偶数节点在后。要求:

1. 给出算法思想
2. 用C语言编写算法
3. 分析时间复杂度和空间复杂度

解题思路:

第一步:审题

• 奇偶节点拆分:经典的双指针问题
• 要求保持原有相对顺序

第二步:选择方法

• 方法1:新建两个链表,分别存储奇数节点和偶数节点
  • 空间复杂度O(n)
• 方法2:原地拆分,用两个指针分别维护奇数链表和偶数链表
  • 空间复杂度O(1)

考场上推荐方法2,因为空间复杂度更低。

第三步:写代码

// 算法思想:
// 1. 创建两个哑结点oddDummy和evenDummy
// 2. 用oddTail和evenTail分别维护奇数链表和偶数链表的尾部
// 3. 遍历原链表,将奇数节点接到oddTail,偶数节点接到evenTail
// 4. 将偶数链表接到奇数链表末尾

LNode* separateOddEven(LNode* head) {
    LNode oddDummy, evenDummy;
    LNode* oddTail = &oddDummy;
    LNode* evenTail = &evenDummy;
    oddDummy.next = NULL;
    evenDummy.next = NULL;
    
    LNode* p = head;
    int index = 1;  // 节点编号(从1开始)
    
    while (p != NULL) {
        if (index % 2 == 1) {
            // 奇数节点
            oddTail->next = p;
            oddTail = oddTail->next;
        } else {
            // 偶数节点
            evenTail->next = p;
            evenTail = evenTail->next;
        }
        p = p->next;
        index++;
    }
    
    // 连接奇数链表和偶数链表
    oddTail->next = evenDummy.next;
    evenTail->next = NULL;  // 防止形成环
    
    return oddDummy.next;
}

第四步:复杂度分析

时间复杂度:

• 遍历链表一次,每个节点访问一次
• 每次访问执行常数个操作
• 设链表长度为n,总操作次数 = O(n)
• 时间复杂度 = O(n)

空间复杂度:

• 只用了常数个指针变量
• 额外空间 = O(1)
• 空间复杂度 = O(1)

答案:

• 算法思想:使用两个哑结点分别维护奇数链表和偶数链表,遍历原链表并分类
• 代码见上
• 时间复杂度O(n),空间复杂度O(1)

涉及知识点: 哑结点技巧、双指针法、链表拆分

命题规律: 本题是408经典题,考察链表的基本操作和哑结点的使用。关键是要掌握"原地拆分"的技巧。

踩坑提醒: ⚠️ 一定要将evenTail->next置为NULL,否则可能形成环。我当年在这里丢了2分。

2.2 命题规律总结

趋势分析:

• 出题频率: 每年必考1道算法设计题,分值15分
• 难度趋势: 稳定在L3级别,不会特别难,但要求代码规范
• 题型偏好: 偏重"双指针法"和"哑结点技巧",几乎每2年考一次快慢指针
• 评分要点:
  • 算法思想(3分):必须清晰、简洁
  • 代码实现(8分):逻辑正确、边界处理完善
  • 复杂度分析(4分):必须有推导过程,不能只写结果

备考建议:

1. 熟练掌握三大方法: 双指针法、递归法、哑结点技巧
2. 代码规范: 变量命名清晰、注释完整、边界处理完善
3. 复杂度分析: 必须有推导过程,不能只写结果
4. 真题练习: 至少做5遍近10年的真题,形成条件反射

模块3:AI命题Prompt ≈ 5000 字

3.1 命题Prompt模板

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

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

📌 章节范围:第1章 线性表
📌 知识点范围:双指针法、递归法、哑结点技巧、复杂度分析

📋 题目要求:
- 题目数量:共12道
- 题型分布:选择题4道、填空题4道、算法设计题4道
- 难度分布:L1基础4道、L2应用4道、L3综合4道

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

请确保题目贴近408真题风格,难度与真题相当。

3.2 AI生成的题目示例

选择题1(L1基础):

题目: 用快慢指针判断单链表是否有环,快指针每次走2步,慢指针每次走1步。如果链表长度为n,则时间复杂度为( ) A. O(1) B. O(log n) C. O(n) D. O(n²)

参考答案: C

解题思路:

• 快指针走了n步到达末尾,慢指针走了n/2步
• 总操作次数 = n + n/2 = 3n/2 = O(n)
• 答案选C

考察知识点: 快慢指针、时间复杂度分析

选择题2(L2应用):

题目: 下列算法中,空间复杂度为O(1)的是( ) A. 递归逆置链表 B. 迭代逆置链表 C. 哈希表判环 D. 新建链表合并

参考答案: B

解题思路:

• A. 递归逆置:递归深度为n,空间复杂度O(n)
• B. 迭代逆置:只用了三个指针变量,空间复杂度O(1)
• C. 哈希表判环:需要存储所有节点,空间复杂度O(n)
• D. 新建链表合并:需要新建链表,空间复杂度O(n)
• 答案选B

考察知识点: 空间复杂度分析、递归vs迭代

填空题1(L2应用):

题目: 用哑结点技巧删除链表中所有值为x的节点,哑结点的作用是________。

参考答案: 统一处理头节点和非头节点的删除操作,避免单独处理边界情况

解题思路:

• 哑结点让头节点的操作与其他节点统一
• 不需要单独判断"删除的是不是头节点"
• 代码更简洁,边界处理更完善

考察知识点: 哑结点技巧、边界处理

算法设计题1(L3综合):

题目: 设计一个算法,将单链表中的所有偶数节点移到奇数节点前面,保持原有相对顺序。要求:

1. 给出算法思想
2. 用C语言编写算法
3. 分析时间复杂度和空间复杂度

参考答案:

// 算法思想:
// 1. 创建两个哑结点evenDummy和oddDummy
// 2. 遍历原链表,将偶数节点接到evenTail,奇数节点接到oddTail
// 3. 将奇数链表接到偶数链表末尾

LNode* separateEvenOdd(LNode* head) {
    LNode evenDummy, oddDummy;
    LNode* evenTail = &evenDummy;
    LNode* oddTail = &oddDummy;
    evenDummy.next = NULL;
    oddDummy.next = NULL;
    
    LNode* p = head;
    while (p != NULL) {
        if (p->data % 2 == 0) {
            evenTail->next = p;
            evenTail = evenTail->next;
        } else {
            oddTail->next = p;
            oddTail = oddTail->next;
        }
        p = p->next;
    }
    
    evenTail->next = oddDummy.next;
    oddTail->next = NULL;
    
    return evenDummy.next;
}

时间复杂度: O(n),遍历链表一次 空间复杂度: O(1),只用了常数个指针变量

考察知识点: 哑结点技巧、链表拆分、复杂度分析

3.3 使用说明

如何使用这个Prompt:

1. 复制Prompt到AI工具(如ChatGPT、Claude、文心一言)
2. 根据需要调整题目数量、题型、难度分布
3. 生成的题目要人工审核,确保质量
4. 建议每次生成后,自己做一遍,对照答案检查

注意事项:

• AI生成的题目可能有错误,一定要人工审核
• 如果题目太难或太简单,可以调整Prompt中的难度分布
• 建议多次生成,挑选质量最好的题目

推荐使用的AI工具:

• ChatGPT-4:质量最高,但需要付费
• Claude:质量较好,免费额度较多
• 文心一言:中文理解更好,适合生成中文题目

模块4:AI讲题Prompt ≈ 5000 字

4.1 讲题Prompt模板

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

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

📌 题目:
设计一个算法,判断单链表中是否存在环。如果存在环,返回环的入口节点;否则返回NULL。

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

📋 特别注意:
- 不要直接给答案,采用引导式提问
- 指出常见的错误思路及为什么错
- 用通俗语言解释抽象概念

4.2 AI生成的讲解示例

题目: 判断单链表中是否存在环,如果存在,返回环的入口节点。

第一步:知识点分析

这道题考察三个知识点:

1. 快慢指针: 判断链表是否有环
2. 数学推导: 为什么快慢指针相遇后,将一个指针放回起点,再次相遇的点就是环入口
3. 代码实现: 如何写出规范的代码

第二步:解题突破口

这道题的关键突破口是:为什么快慢指针相遇后,将一个指针放回起点,再次相遇的点就是环入口?

让我用通俗的语言解释:

假设:

• 链表起点到环入口的距离为a
• 环入口到快慢指针相遇点的距离为b
• 环的周长为c

当快慢指针相遇时:

• 慢指针走了a + b步
• 快指针走了a + b + kc步(k为快指针在环中转的圈数)

因为快指针速度是慢指针的2倍:

这个等式的含义是:

• 从起点走a步到达环入口
• 从相遇点走(c-b)步也到达环入口(因为环的周长是c)
• 如果k>1,快指针在环中多转了(k-1)圈

所以,将一个指针放回起点,两个指针每次都走1步:

• 起点指针走a步到达环入口
• 相遇点指针走(c-b)步到达环入口(可能多转了几圈)
• 两者同时到达环入口,再次相遇

第三步:逐步推导

1. 初始化: slow和fast都指向head
2. 判断是否有环:
   • slow每次走1步,fast每次走2步
   • 如果fast到达末尾(NULL),说明无环
   • 如果slow == fast,说明有环
3. 找环入口:
   • 将ptr指向head,slow保持在相遇点
   • ptr和slow每次都走1步
   • 当ptr == slow时,即为环入口

第四步:通用解法总结

快慢指针的通用解法:

1. 判断是否有环: 快指针每次走2步,慢指针每次走1步,看是否相遇
2. 找环入口: 相遇后,一个指针放回起点,两个指针每次都走1步,再次相遇的点即为入口
3. 找中点: 快指针每次走2步,慢指针每次走1步,快指针到达末尾时,慢指针在中点

第五步:变式题

变式题1: 已知单链表有环,求环的长度。

解答:

• 用快慢指针找到相遇点
• 从相遇点出发,继续走,再次回到相遇点时,走过的步数就是环的长度

变式题2: 已知单链表有环,求环的入口节点(用哈希表方法)。

解答:

• 遍历链表,将每个节点存入哈希表
• 如果遇到已存在的节点,即为环入口
• 时间复杂度O(n),空间复杂度O(n)

4.3 易错题记录

易错题1: 快慢指针判环,快指针的终止条件写错

错误表现:

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

正确做法:

while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

原因: fast->next->next需要fast->next不为NULL,否则段错误。

易错题2: 递归逆置链表,忘记将head接到子链表末尾

错误表现:

LNode* reverse(LNode* head) {
    if (head == NULL || head->next == NULL) return head;
    reverse(head->next);
    // 忘记合并结果
}

正确做法:

LNode* reverse(LNode* head) {
    if (head == NULL || head->next == NULL) return head;
    LNode* newHead = reverse(head->next);
    head->next->next = head;  // 合并结果
    head->next = NULL;
    return newHead;
}

原因: 递归三步(终止条件、递归调用、合并结果)缺一不可。

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

5.1 错题复盘Prompt模板

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

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

📌 我的错题:
设计一个算法,将单链表逆置。我写了以下代码:

LNode* reverse(LNode* head) {
    LNode* prev = NULL;
    LNode* curr = head;
    while (curr != NULL) {
        curr->next = prev;
        prev = curr;
        curr = curr->next;
    }
    return prev;
}

但运行后发现链表断了,只保留了第一个节点。

📌 正确答案:
LNode* reverse(LNode* head) {
    LNode* prev = NULL;
    LNode* curr = head;
    while (curr != NULL) {
        LNode* next = curr->next;  // 保存后继
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

📋 分析要求:
1. 【错因诊断】分析我出错的根本原因
2. 【知识漏洞定位】指出我需要回看的教材章节
3. 【正确思路】给出正确的解题思路
4. 【强化训练】针对我的薄弱环节,出3道同类型练习题
5. 【防错提醒】总结一句"下次遇到类似题一定要注意..."的提醒

5.2 AI生成的复盘示例

【错因诊断】

你的错误在于:在修改curr->next之前,没有保存curr的后继节点。

具体分析:

curr->next = prev;  // 修改了curr->next
prev = curr;        // prev后移
curr = curr->next;  // 此时curr->next已经是prev了,不是原来的后继

执行完curr->next = prev后,curr->next指向了prev,不再是原来的后继节点。所以curr = curr->next实际上是curr = prev,导致链表断裂。

根本原因: 对链表指针操作的理解不够深入,没有意识到"修改指针前要先保存原值"。

【知识漏洞定位】

你需要回看:

• 严蔚敏《数据结构(C语言版)》P38-40:单链表的插入和删除操作
• 王道考研《数据结构复习指导》P25-28:链表的基本操作

重点理解:

• 修改指针前,为什么要先保存后继节点
• 链表操作中,哪些步骤是有顺序要求的

【正确思路】

正确的迭代逆置思路:

1. 用prev指向已逆置部分的头,初始为NULL
2. 用curr指向当前节点,初始为head
3. 遍历链表,对每个节点:
   • 先保存后继: next = curr->next
   • 反转指针: curr->next = prev
   • prev后移: prev = curr
   • curr后移: curr = next
4. 返回prev,即逆置后的头

关键点:在修改curr->next之前,必须先保存curr->next。

【强化训练】

练习题1(L1基础): 删除单链表中值为x的所有节点,写出代码。

参考答案:

void deleteAllX(LNode* head, int x) {
    LNode dummy;
    dummy.next = head;
    LNode* p = &dummy;
    while (p->next != NULL) {
        if (p->next->data == x) {
            LNode* temp = p->next;
            p->next = p->next->next;
            free(temp);
        } else {
            p = p->next;
        }
    }
}

练习题2(L2应用): 合并两个有序链表,写出代码。

参考答案:

LNode* merge(LNode* L1, LNode* L2) {
    LNode dummy;
    LNode* tail = &dummy;
    LNode* p = L1;
    LNode* q = L2;
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }
    tail->next = (p != NULL) ? p : q;
    return dummy.next;
}

练习题3(L3综合): 将单链表的每两个节点一组进行逆置,如1→2→3→4变为2→1→4→3。

参考答案:

LNode* swapPairs(LNode* head) {
    if (head == NULL || head->next == NULL) return head;
    LNode* newHead = head->next;
    head->next = swapPairs(newHead->next);
    newHead->next = head;
    return newHead;
}

【防错提醒】

下次遇到链表指针操作题,一定要注意:修改指针前,先保存原值。特别是curr->next = xxx这种操作,一定要先next = curr->next保存后继。

记住口诀:“先存后改再后移”——先保存后继,再修改指针,最后后移指针。

5.3 错题归因统计

主要薄弱环节: 指针操作(50%)和边界条件(27%)

改进建议:

1. 多做链表基础题,熟练掌握指针操作
2. 每次写完代码,先检查边界条件(空链表、头节点)
3. 用哑结点技巧统一处理边界情况

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

6.1 模拟卷Prompt模板

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

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

📌 章节范围:第1章 线性表
📌 知识点范围:双指针法、递归法、哑结点技巧、复杂度分析

📋 试卷结构:
- 选择题:5道,每题5分,共25分
- 填空题:5道,每题5分,共25分
- 算法设计题:3道,共50分
- 总分:100分
- 建议用时:120分钟

📋 难度分布:
- 基础题(L1-L2):占40%
- 中等题(L3):占40%
- 较难题(L4):占20%

📋 输出要求:
1. 先输出完整试卷(不含答案)
2. 然后输出参考答案与评分标准
3. 每道算法设计题标注"踩分点"
4. 最后给出分数段评估建议:
   - 90分以上:掌握优秀,可以继续下一章
   - 75-89分:掌握良好,建议复习薄弱点
   - 60-74分:基本掌握,建议重点复习本章
   - 60分以下:基础不牢,建议重新学习本章

6.2 AI生成的完整模拟卷

408数据结构·第1章线性表模拟卷

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

一、选择题(每题5分,共25分)

1. 用快慢指针找单链表的中点,当链表长度为偶数时,慢指针指向( ) A. 第n/2个节点 B. 第n/2+1个节点 C. 第n/2个或第n/2+1个节点(取决于实现) D. 无法确定
2. 下列算法中,时间复杂度为O(n²)的是( ) A. 双指针找倒数第k个节点 B. 迭代逆置链表 C. 在单链表中查找值为x的节点 D. 以上都不是
3. 使用哑结点技巧的好处是( ) A. 减少时间复杂度 B. 减少空间复杂度 C. 统一处理边界情况,简化代码 D. 提高代码运行速度
4. 递归逆置链表的空间复杂度是( ) A. O(1) B. O(log n) C. O(n) D. O(n²)
5. 判断单链表是否有环,最优的空间复杂度是( ) A. O(1) B. O(log n) C. O(n) D. O(n²)

二、填空题(每题5分,共25分)

1. 用快慢指针判断链表是否有环,快指针每次走2步,慢指针每次走1步。如果链表有环,快慢指针一定会________。
2. 递归法的三要素是:________、递归调用、合并结果。
3. 哑结点的作用是________,让头节点的操作与其他节点统一。
4. 迭代逆置链表时,需要三个指针:prev、curr和________。
5. 合并两个有序链表的时间复杂度是________。

三、算法设计题(共50分)

1. (15分)设计一个算法,删除单链表中所有值为x的节点。要求:
   • 给出算法思想
   • 用C语言编写算法
   • 分析时间复杂度和空间复杂度
2. (15分)设计一个算法,找出单链表的倒数第k个节点。要求:
   • 给出算法思想
   • 用C语言编写算法
   • 分析时间复杂度和空间复杂度
3. (20分)设计一个算法,将单链表的所有奇数节点和偶数节点分开,奇数节点在前,偶数节点在后,保持原有相对顺序。要求:
   • 给出算法思想
   • 用C语言编写算法
   • 分析时间复杂度和空间复杂度

参考答案与评分标准

一、选择题

1. C 解析:当链表长度为偶数时,慢指针可能指向第n/2个或第n/2+1个节点,取决于快指针的终止条件。 评分:选对得5分,选错得0分。
2. D 解析:A、B、C的时间复杂度都是O(n),没有O(n²)的算法。 评分:选对得5分,选错得0分。
3. C 解析:哑结点的好处是统一处理边界情况,简化代码,不改变时间/空间复杂度。 评分:选对得5分,选错得0分。
4. C 解析:递归深度为n,每层需要O(1)的栈空间,总空间复杂度O(n)。 评分:选对得5分,选错得0分。
5. A 解析:快慢指针判环的空间复杂度是O(1),只需要两个指针变量。 评分:选对得5分,选错得0分。

二、填空题

1. 相遇 评分:填对得5分,填错得0分。
2. 递归终止条件 评分:填对得5分,填错得0分。
3. 避免单独处理头节点 评分:填对得5分,填错得0分。
4. next 评分:填对得5分,填错得0分。
5. O(n) 评分:填对得5分,填错得0分。

三、算法设计题

第11题(15分)

算法思想(3分): 使用哑结点统一处理所有节点,遍历链表并删除值为x的节点。

代码实现(8分):

void deleteAllX(LNode* head, int x) {
    LNode dummy;           // 2分
    dummy.next = head;
    LNode* p = &dummy;     // 1分
    while (p->next != NULL) {  // 2分
        if (p->next->data == x) {  // 1分
            LNode* temp = p->next;
            p->next = p->next->next;
            free(temp);      // 1分
        } else {
            p = p->next;     // 1分
        }
    }
}

复杂度分析(4分):

• 时间复杂度:O(n),遍历链表一次(2分)
• 空间复杂度:O(1),只用了常数个指针变量(2分)

踩分点:

• 哑结点的创建和使用(2分)
• 遍历和删除逻辑(3分)
• 释放内存(1分)
• 复杂度分析(4分)

第12题(15分)

算法思想(3分): 快指针先走k步,然后快慢指针一起走,当快指针到达末尾时,慢指针在倒数第k个。

代码实现(8分):

LNode* findKthFromEnd(LNode* head, int k) {
    if (head == NULL || k <= 0) return NULL;  // 1分
    LNode* fast = head;
    LNode* slow = head;
    for (int i = 0; i < k; i++) {  // 2分
        if (fast == NULL) return NULL;  // 1分
        fast = fast->next;
    }
    while (fast != NULL) {  // 2分
        fast = fast->next;
        slow = slow->next;
    }
    return slow;  // 2分
}

复杂度分析(4分):

• 时间复杂度:O(n),快指针走了n步(2分)
• 空间复杂度:O(1),只用了两个指针变量(2分)

踩分点:

• 快指针先走k步(2分)
• 检查k是否大于链表长度(1分)
• 快慢指针一起走(2分)
• 复杂度分析(4分)

第13题(20分)

算法思想(4分): 使用两个哑结点分别维护奇数链表和偶数链表,遍历原链表并分类,最后连接两个链表。

代码实现(10分):

LNode* separateOddEven(LNode* head) {
    LNode oddDummy, evenDummy;      // 2分
    LNode* oddTail = &oddDummy;
    LNode* evenTail = &evenDummy;
    oddDummy.next = NULL;
    evenDummy.next = NULL;
    
    LNode* p = head;
    int index = 1;
    while (p != NULL) {             // 2分
        if (index % 2 == 1) {       // 2分
            oddTail->next = p;
            oddTail = oddTail->next;
        } else {
            evenTail->next = p;
            evenTail = evenTail->next;
        }
        p = p->next;
        index++;
    }
    oddTail->next = evenDummy.next; // 2分
    evenTail->next = NULL;          // 2分
    return oddDummy.next;
}

复杂度分析(6分):

• 时间复杂度:O(n),遍历链表一次(3分)
• 空间复杂度:O(1),只用了常数个指针变量(3分)

踩分点:

• 两个哑结点的创建(2分)
• 分类逻辑(2分)
• 连接两个链表(2分)
• 防止形成环(evenTail->next = NULL)(2分)
• 复杂度分析(6分)

6.3 评分标准参考

分数段评估建议:

• 90-100分: 掌握优秀,可以继续下一章
  • 建议:可以做更难的题目,如408真题的压轴题
• 75-89分: 掌握良好,但有薄弱点
  • 建议:复习错题对应的知识点,重点练习双指针和递归
• 60-74分: 基本掌握,但需要加强
  • 建议:重新学习本章,重点练习代码实现和复杂度分析
• 60分以下: 基础不牢,建议重新学习本章
  • 建议:先复习DS-01-01到DS-01-05,掌握基本操作后再做算法题

评分细则:

• 算法思想:3-4分,要求清晰、简洁
• 代码实现:8-10分,要求逻辑正确、边界处理完善
• 复杂度分析:4-6分,要求有推导过程,不能只写结果

模块7:延伸阅读 ≈ 3000 字

7.1 教材参考

• 严蔚敏《数据结构(C语言版)》 第2章"线性表",P22-58
  • 重点阅读:单链表的插入和删除操作(P38-40),理解指针操作的顺序
  • 适合人群:基础薄弱的同学,讲解详细,例题丰富
• 王道考研《数据结构复习指导》 第2章"线性表",P18-62
  • 重点阅读:算法题解题方法(P32-45),双指针法和哑结点技巧
  • 适合人群:备考408的同学,贴近真题,技巧实用
• 邓俊辉《数据结构(C++语言版)》 第2章"线性表",P45-89
  • 重点阅读:链表的高级应用(P70-89),递归法解链表题
  • 适合人群:想深入理解的同学,讲解透彻,代码规范

7.2 视频课程

• [B站]王道考研数据结构 - 推荐观看第2章"线性表"
  • 讲师:王道团队
  • 特点:贴近408真题,讲解清晰,适合备考
  • 推荐章节:2.3单链表、2.4双链表和循环链表
• [B站]青岛大学-数据结构 - 推荐观看第2章"线性表"
  • 讲师:某教授
  • 特点:讲解详细,适合基础薄弱的同学
  • 推荐章节:2.3线性表的链式表示
• [慕课]清华大学-数据结构 - 推荐观看第3章"线性结构"
  • 讲师:邓俊辉教授
  • 特点:讲解深入,代码规范,适合想深入理解的同学
  • 推荐章节:3.3链表、3.4递归

7.3 知识关联图

前置知识:

• DS-01-01到DS-01-05:线性表的基本操作,是算法题的基础
• 必须熟练掌握初始化、插入、删除、遍历等基本操作

后续知识:

• DS-01-07和DS-01-08:真题练习和模拟演练,巩固本节内容
• DS-04-03(图的遍历):BFS和DFS中会用到双指针法
• DS-06-03(快速排序):分区算法中会用到对撞指针
• DS-07-02(分治法):递归法是分治法的基础

学习路径建议:

1. 先掌握DS-01-01到DS-01-05的基本操作
2. 学习本节的三大方法(双指针、递归、哑结点)
3. 做DS-01-07和DS-01-08的真题练习
4. 在后续章节中应用这些方法

模块8:本章Checklist ≈ 2500 字

8.1 知识点清单

• 双指针法: 能解释快慢指针、对撞指针、滑动窗口的原理和适用场景
• 快慢指针找中点: 能写出代码,并分析快指针的终止条件
• 快慢指针判环: 能写出代码,并证明为什么快慢指针会相遇
• 快慢指针找环入口: 能写出代码,并推导为什么再次相遇的点是入口
• 递归法三要素: 能说出递归终止条件、递归调用、合并结果的含义
• 递归逆置链表: 能写出递归版本和迭代版本的代码
• 递归vs迭代: 能对比两者的时间复杂度和空间复杂度
• 哑结点技巧: 能解释哑结点的作用,并写出使用哑结点的代码
• 删除指定值: 能用哑结点技巧删除链表中所有值为x的节点
• 合并有序链表: 能用双指针法合并两个有序链表
• 奇偶拆分: 能用哑结点技巧将链表按奇偶拆分
• 时间复杂度分析: 能规范地推导时间复杂度,并写出推导过程
• 空间复杂度分析: 能规范地推导空间复杂度,区分递归和迭代的空间复杂度
• 边界条件处理: 能识别并处理空链表、头节点等边界情况
• 代码规范: 变量命名清晰、注释完整、逻辑正确

8.2 自测问题

概念理解题:

1. Q: 快慢指针判环,为什么快慢指针一定会相遇? A: 因为快指针每次比慢指针多走1步,如果链表有环,快指针会在环中追上慢指针。
2. Q: 递归法的三要素是什么? A: 递归终止条件、递归调用、合并结果。
3. Q: 哑结点的作用是什么? A: 统一处理头节点和非头节点的操作,避免单独处理边界情况。

公式应用题:

1. Q: 用快慢指针找链表中点,时间复杂度是多少? A: O(n)。快指针走了n步,慢指针走了n/2步,总操作次数O(n)。
2. Q: 递归逆置链表的空间复杂度是多少? A: O(n)。递归深度为n,每层需要O(1)的栈空间。
3. Q: 合并两个有序链表的时间复杂度是多少? A: O(n)。需要遍历两个链表的所有节点。

综合分析题:

1. Q: 如何判断一个链表算法题应该用双指针还是递归? A: 如果题目涉及"找第k个"“判断环”“找中点”,用双指针;如果题目涉及"逆置"“拆分”“合并”,用递归或迭代。
2. Q: 哑结点技巧适用于哪些场景? A: 删除指定值、合并链表、在头部插入节点等可能修改头指针的场景。

易错辨析题:

1. Q: 快慢指针判环,快指针的终止条件是什么?为什么? A: fast != NULL && fast->next != NULL。因为fast->next->next需要fast->next不为NULL。
2. Q: 递归逆置链表时,为什么要有head->next = NULL这一步? A: 防止形成环。逆置后,head变成尾节点,需要将它的next置为NULL。
3. Q: 使用哑结点时,为什么最后要返回dummy->next而不是dummy? A: 因为哑结点本身不存储数据,真正的第一个节点是dummy->next。

8.3 完成度评估

整体掌握程度评估:

• 如果8个模块全部完成,且模拟卷得分≥90分:掌握优秀,可以继续下一章
• 如果完成6-7个模块,且模拟卷得分75-89分:掌握良好,建议复习薄弱点
• 如果完成4-5个模块,且模拟卷得分60-74分:基本掌握,建议重点复习本章
• 如果完成<4个模块,且模拟卷得分<60分:基础不牢,建议重新学习本章

下一步学习建议:

• 完成本节后,继续学习DS-01-07(高频真题与易错点总结)和DS-01-08(真题解析与模拟演练)
• 在做后续章节的算法题时,有意识地应用本节学到的三大方法
• 定期复习本节内容,防止遗忘

在这里插入图片描述