链表模拟题谈模拟题的通用解题思维
2026-07-26 14:30:43
发布于：云南
18阅读
0回复
0点赞
最近在刷ACGO基础模拟题库时，遇到了一道双向链表模拟队列插入与删除的经典题目。一开始上手的时候，我总觉得模拟题“照着题意写就行”，结果实操中频繁出现指针错乱、删重、边界漏判等问题。
写完、调通、复盘完整套流程之后，我突然意识到：模拟题从来不是“暴力翻译题意”，而是在代码里搭建一套稳定、自洽、容错的微型系统。
这篇帖子就结合这道链表题，分享一下我总结出的模拟题通用做题方法、踩坑点以及思维习惯，适合刚入门算法、经常写挂模拟题的同学参考。
一、很多新手的误区：模拟题=无脑翻译题目
最开始学算法的时候，我一直有个误区：贪心、DP、图论需要思维，模拟题只要细心就行。
但真正多刷几道高质量模拟题后会发现：模拟题最考验的是对「过程、状态、边界、容错」的掌控力。
比如这道队列链表题，看似只有两个操作：
- 依次把新同学插入指定位置的左边/右边
- 批量删除指定编号的同学，重复删除不报错
如果只是照着样例手写几组数据，很容易写对；但一旦数据量大、操作混杂，就会出现：指针断链、节点重复指向、删除后仍参与遍历、重复删除出错等隐性bug。
这也是很多同学模拟题：小数据能过、大数据必挂、样例全对但是WA一片的根本原因。
二、本题核心思路：用数组模拟双向链表的优势
很多新手第一反应是用STL链表，但在竞赛场景里，数组模拟双向链表永远是最优解。
原因很简单：
- 编号连续、定点查找 O(1)，不需要遍历查找节点
- 插入、删除操作均为纯指针修改，时间复杂度极低，能扛满数据范围
- 逻辑完全可控，没有STL迭代器失效、遍历异常等玄学问题
我们只需要两个核心数组维护状态：
- pre[x]：编号 x 的前驱节点
- nxt[x]：编号 x 的后继节点
再搭配一个删除标记数组，就可以完美处理「重复删除、已删节点不参与运算」的容错需求。整套结构非常简洁，且完全贴合题意。
三、关键操作逻辑拆解（新手最容易写错的地方）
我复盘了自己最初写错的地方，基本都集中在「插入时四条指针的修改顺序」和「删除时前后节点的衔接」。
- 向左插入（插在指定节点左侧）
很多同学会习惯性先改目标节点的前驱，导致原前驱节点地址丢失，直接断链。
正确顺序一定是：先保住旧链接，再新建链接。
先记录当前节点的前驱，让新节点承接旧前驱，再让原节点和旧前驱指向新节点，全程不会丢状态。 - 向右插入（插在指定节点右侧）
逻辑和左插对称，核心同理：先保存原节点后继，再完成新节点的双向绑定，最后修补原链关系。只要顺序不乱，基本不会出错。 - 删除操作的核心容错
题目有一个很关键的隐藏条件：同一个节点可能被多次删除，需忽略重复删除操作。
所以必须加删除标记：每次删除前先判断是否已被删除，未删除才执行断链操作，同时打上标记。
删除的本质只有一步：让前驱和后继直接互通，跳过当前节点。被删掉的节点从此脱离链表，遍历完全不会访问到。
四、模拟题通用高分思维（适用于所有模拟题型）
做完这道题，我总结了一套自己后续通用的模拟解题流程，非常适合新手养成规范做题习惯：
- 先建状态，再写操作
不着急写逻辑，先想清楚：本题需要哪些数组、哪些标记、初始状态是什么。状态定义清楚，代码就成功一半。 - 所有操作遵守“先保旧，再更新”
无论是交换、插入、覆盖，优先保留原始数据，再修改新数据，杜绝丢状态bug。 - 所有删除、修改操作默认容错
提前考虑重复操作、空边界、已失效节点，不要依赖题目保证数据合法。 - 最后统一遍历输出，不边算边输出
边运算边输出极其容易乱序、漏输出，全部处理完再遍历，逻辑更干净、调试更方便。
hhh
十分简单
题目（自己出的）
约瑟夫环变种（链表删除高频考点）
题目大意
n 个人围成一圈环形链表，从 1 号开始报数，数到第 k 个人就将其移出环，不断重复直到只剩最后 1 个人，输出最后留存的编号。
思路
环形双向链表：首尾互相指向，循环查找 + 节点删除，完美练习循环链表删除操作。
完整代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int pre[MAXN],nxt[MAXN];
int n,k;
int main(){
cin>>n>>k;
// 构建环形链表
for(int i=1;i<=n;i++){
pre[i]=i-1;
nxt[i]=i+1;
}
pre[1]=n; nxt[n]=1;
int cnt=n,cur=1;
while(cnt>1){
// 走k-1步找到要删的人
for(int i=1;i<k;i++) cur=nxt[cur];
// 删除cur节点
nxt[pre[cur]]=nxt[cur];
pre[nxt[cur]]=pre[cur];
cur=nxt[cur];
cnt--;
}
cout<<cur;
return 0;
}
这里空空如也
有帮助，赞一个