算法题解：单链表的高效实现（含经典致命错误深度剖析）

算法题解单链表的高效实现含经典致命错误深度剖析本文对应AcWing 826. 单链表是链表入门的必做经典题。本文不仅会给出完整可运行的代码还会深度拆解90%初学者都会踩的致命坑帮你彻底搞懂链表的指针操作逻辑。一、题目描述实现一个初始为空的单链表支持以下三种操作H x向链表头插入一个数xD k删除第 k 个插入的数后面的一个数当k0时表示删除头结点I k x在第 k 个插入的数后面插入一个数xk恒大于0进行完M次操作后从头到尾输出整个链表。⚠️核心注意点题目中第 k 个插入的数≠当前链表的第 k 个数。它指的是按照插入时间顺序编号的节点即使某个节点被删除了后续节点的编号也不会改变。数据范围1 ≤ M ≤ 100000二、解题核心思路2.1 为什么不能用普通指针遍历如果每次执行D k或I k x操作时都从头遍历链表找到第 k 个节点那么单次操作的时间复杂度是O(n)总时间复杂度会达到O(n²)。对于M1e5的数据量这种写法会直接超时。2.2 最优解法数组映射法我们用一个全局数组来记录每个插入节点的指针数组下标就是节点的插入编号。这样我们就能在O(1)时间内找到任意一个历史插入的节点所有操作的总时间复杂度降为O(n)。sort[i]存储第i个插入的节点的指针sort_count记录已经插入的节点总数作为下一个节点的编号三、代码实现与经典错误剖析3.1 错误代码90%初学者都会写错先看大家最容易写出的错误版本重点关注del函数// 错误的del函数voiddel(intx){if(x0){// 删除头结点这部分是对的node*temlist.Head;list.Headlist.Head-next;deletetem;}else{node*temlist.sort[x]-next;// 要删除的节点// ❌ 致命错误修改了sort数组list.sort[x]tem-next;deletetem;}}错误原因深度解析sort数组的作用是记录历史插入节点的指针它是一个只读的映射表绝对不能修改我们要删除的是第 x 个插入的节点后面的节点正确的逻辑应该是让第 x 个节点的next指针直接指向被删除节点的下一个节点而不是把sort[x]本身改成被删除节点的下一个节点。这会导致后续所有引用sort[x]的操作都指向错误的节点彻底破坏链表结构。3.2 测试用例错误过程演示用你提供的测试用例一步步看错误是如何发生的输入 10 H 2 // 第1个插入节点1(2) D 0 // 删除头结点节点1 H 6 // 第2个插入节点2(6) H 8 // 第3个插入节点3(8) I 2 5 // 第4个插入节点4(5)插在节点2后面 I 2 3 // 第5个插入节点5(3)插在节点2后面 I 4 6 // 第6个插入节点6(6)插在节点4后面 I 3 4 // 第7个插入节点7(4)插在节点3后面 D 3 // 删除第3个插入的节点节点3后面的节点节点7 I 3 6 // 第8个插入节点8(6)插在节点3后面错误代码执行到D 3时本来应该执行节点3-next 节点7-next也就是NULL但错误代码执行了sort[3] 节点7-next也就是NULL后续执行I 3 6时代码会尝试在sort[3]现在是NULL后面插入节点8这本来应该崩溃但由于内存未初始化等原因实际会出现不可预期的行为最终导致输出错误3.3 修正后的完整可运行代码#includestdio.h// 链表节点结构体structnode{intvalue;// 节点存储的值node*next;// 指向下一个节点的指针};// 链表整体结构体structLinkedList{node*Head;// 链表头指针node*sort[100005];// 映射表sort[i] 第i个插入的节点的指针intsort_count;// 已插入节点的总数};LinkedList list;// 全局链表实例避免栈溢出// 初始化链表voidinit_list(){list.HeadNULL;list.sort_count0;}// 头插法在链表头部插入值为x的节点voidhead(intx){node*new_nodenewnode{x,NULL};new_node-nextlist.Head;list.Headnew_node;// 记录新节点的插入顺序list.sort[list.sort_count]new_node;}// 删除第x个插入的节点后面的节点voiddel(intx){if(x0){// 删除头结点node*temlist.Head;list.Headlist.Head-next;deletetem;}else{node*prelist.sort[x];// 前一个节点node*del_nodepre-next;// 要删除的节点// ✅ 正确写法修改前一个节点的next指针pre-nextdel_node-next;deletedel_node;}}// 在第x个插入的节点后面插入值为y的节点voidinsert(intx,inty){node*new_nodenewnode{y,NULL};node*prelist.sort[x];// 找到前一个节点// 标准链表插入操作new_node-nextpre-next;pre-nextnew_node;// 记录新节点的插入顺序list.sort[list.sort_count]new_node;}intmain(){intm;scanf(%d,m);init_list();for(inti0;im;i){charop;scanf( %c,op);// 前面的空格用于吸收换行符switch(op){caseH:{intx;scanf(%d,x);head(x);break;}caseD:{intx;scanf(%d,x);del(x);break;}caseI:{intx,y;scanf(%d %d,x,y);insert(x,y);break;}}}// 遍历输出链表node*curlist.Head;while(cur!NULL){printf(%d ,cur-value);curcur-next;}return0;}3.4 测试结果输入上述测试用例输出结果为8 6 6 3 5 6与标准答案完全一致。四、关键知识点总结数组映射法是处理第k个插入节点问题的标准解法时间复杂度最优sort数组是只读的只能用来记录节点指针绝对不能修改它的值链表删除操作的本质是修改前一个节点的next指针让它跳过被删除的节点全局变量分配在静态存储区不会出现栈溢出问题适合存储大数组题目保证所有操作合法因此可以省略一些空指针判断提高运行效率五、拓展思考如果题目要求支持删除第k个插入的节点本身代码应该怎么修改这种用数组模拟链表的方式和用std::list相比有什么优缺点如果需要支持双向链表的操作这个思路还能用吗如果这篇博客对你有帮助欢迎点赞收藏关注有任何问题都可以在评论区留言交流~