当前位置：首页 > news >正文

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

news 2026/4/21 6:41:50

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

本文对应AcWing 826. 单链表，是链表入门的必做经典题。本文不仅会给出完整可运行的代码，还会深度拆解90%初学者都会踩的致命坑，帮你彻底搞懂链表的指针操作逻辑。

一、题目描述

实现一个初始为空的单链表，支持以下三种操作：

H x：向链表头插入一个数x
D k：删除第 k 个插入的数后面的一个数（当k=0时，表示删除头结点）
I k x：在第 k 个插入的数后面插入一个数x（k恒大于0）

进行完M次操作后，从头到尾输出整个链表。

⚠️核心注意点：题目中"第 k 个插入的数"≠"当前链表的第 k 个数"。它指的是按照插入时间顺序编号的节点，即使某个节点被删除了，后续节点的编号也不会改变。

数据范围：1 ≤ M ≤ 100000

二、解题核心思路

2.1 为什么不能用普通指针遍历？

如果每次执行D k或I k x操作时，都从头遍历链表找到第 k 个节点，那么单次操作的时间复杂度是O(n)，总时间复杂度会达到O(n²)。对于M=1e5的数据量，这种写法会直接超时。

2.2 最优解法：数组映射法

我们用一个全局数组来记录每个插入节点的指针，数组下标就是节点的插入编号。这样我们就能在O(1)时间内找到任意一个历史插入的节点，所有操作的总时间复杂度降为O(n)。

sort[i]：存储第i个插入的节点的指针
sort_count：记录已经插入的节点总数，作为下一个节点的编号

三、代码实现与经典错误剖析

3.1 错误代码（90%初学者都会写错）

先看大家最容易写出的错误版本，重点关注del函数：

// 错误的del函数voiddel(intx){if(x==0){// 删除头结点（这部分是对的）node*tem=list.Head;list.Head=list.Head->next;deletetem;}else{node*tem=list.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 修正后的完整可运行代码

#include<stdio.h>// 链表节点结构体structnode{intvalue;// 节点存储的值node*next;// 指向下一个节点的指针};// 链表整体结构体structLinkedList{node*Head;// 链表头指针node*sort[100005];// 映射表：sort[i] = 第i个插入的节点的指针intsort_count;// 已插入节点的总数};LinkedList list;// 全局链表实例（避免栈溢出）// 初始化链表voidinit_list(){list.Head=NULL;list.sort_count=0;}// 头插法：在链表头部插入值为x的节点voidhead(intx){node*new_node=newnode{x,NULL};new_node->next=list.Head;list.Head=new_node;// 记录新节点的插入顺序list.sort[++list.sort_count]=new_node;}// 删除第x个插入的节点后面的节点voiddel(intx){if(x==0){// 删除头结点node*tem=list.Head;list.Head=list.Head->next;deletetem;}else{node*pre=list.sort[x];// 前一个节点node*del_node=pre->next;// 要删除的节点// ✅ 正确写法：修改前一个节点的next指针pre->next=del_node->next;deletedel_node;}}// 在第x个插入的节点后面插入值为y的节点voidinsert(intx,inty){node*new_node=newnode{y,NULL};node*pre=list.sort[x];// 找到前一个节点// 标准链表插入操作new_node->next=pre->next;pre->next=new_node;// 记录新节点的插入顺序list.sort[++list.sort_count]=new_node;}intmain(){intm;scanf("%d",&m);init_list();for(inti=0;i<m;i++){charop;scanf(" %c",&op);// 前面的空格用于吸收换行符switch(op){case'H':{intx;scanf("%d",&x);head(x);break;}case'D':{intx;scanf("%d",&x);del(x);break;}case'I':{intx,y;scanf("%d %d",&x,&y);insert(x,y);break;}}}// 遍历输出链表node*cur=list.Head;while(cur!=NULL){printf("%d ",cur->value);cur=cur->next;}return0;}