今日学习内容#

2h，系统复习并实操了数据结构线性表章节中单链表的核心知识点，包括单链表的结构定义、创建（头插法/尾插法）、插入、删除、按值查找、按位查找操作，以及考研高频考点：链表逆置、快慢指针判环与找环入口。

AI知识点带复盘#

单链表是408数据结构线性表章节的核心必考考点，以下是本次学习的考点复盘与拓展：

1. 基础操作考点 单链表的标准结构定义为typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;，选择题常考察该结构的内存分配细节、算法复杂度（插入/删除操作仅需O(1)时间复杂度，查找为O(n)）。
2. 头插法与尾插法辨析
   • 头插法：无需维护尾指针，每次新建节点后直接将其next指向头节点的next，再修改头节点的next指向新节点，最终生成的链表与输入顺序相反，常用于快速实现链表逆置。
   • 尾插法：需要维护尾指针LNode *tail，每次新建节点后将tail->next指向新节点，再将tail更新为新节点，循环结束后需将tail->next置为NULL，避免出现野指针，最终生成的链表与输入顺序一致。
3. 高频变形题型考点
   • 链表逆置：可通过头插法遍历原链表逐个插入新链表实现，或通过迭代修改节点指针方向实现，两种方法时间复杂度均为O(n)，空间复杂度为O(1)。
   • 快慢指针判环：快指针步长为2，慢指针步长为1，若链表存在环，则二者必然在环内相遇；若要找环入口，可在相遇后将慢指针重置到头节点，二者以相同步长移动，再次相遇点即为环入口，该结论可通过相对运动与数学推导验证。
   • 其他常考题型：删除指定位置节点、找链表中间节点、合并有序单链表、删除链表倒数第N个节点等。

问题与反思#

1. 实操编写单链表删除指定位置节点代码时，忘记处理删除头节点的特殊情况，导致代码在删除第一个节点时出现指针越界错误；
2. 对快慢指针找环入口的数学推导不够熟练，仅能记住解题结论，无法独立完成完整推导过程；
3. 尾插法的循环终止条件容易混淆，曾误将条件写为p != NULL而非p->next != NULL，导致创建的链表多出一个空的头节点后置节点。

收获与总结#

1. 掌握了单链表所有基础操作的规范实现，能够快速写出无边界错误的可运行代码；
2. 清晰区分了头插法与尾插法的适用场景与实现细节，能够根据需求快速选择合适的创建方式；
3. 理解了快慢指针判环及找环入口的原理，能够独立完成相关题型的推导与代码实现；
4. 总结了单链表编程题的5类常见易错点，后续刷题时可针对性规避错误。

💡 碎碎念：踏实吃透每一个知识点！

文档内容由 AI 辅助生成