自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:03，当前版本为作者最后更新于2022-05-21 16:42:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3631 单向链表 題解

管理员注：

阅读本文章前，请先阅读$\ \texttt{ShanCreeper}$ B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

维护一张初始只有元素 $1$ 的表，支持以下操作：

• $1 \ x \ y$：将元素 $y$ 插入到 $x$ 后；
• $2 \ x$：询问 $x$ 后面的元素是什么；
• $3 \ x$：从表中删除 $x$ 后的元素。

如果有操作二，输出一个数字，并换行。

我们依旧可以看成一些人在排队，只不过多了一个插队和走人的操作。

我们假设初始排队顺序为：$1 \ 4 \ 2 \ 3$。

若 5 号同学插队到 4 号的后面，那么会发生什么？

我们先来看看初始的链表情况：

此时，5 号同学插入 4 号的后面，那么链表就会变为：

此时 2 4 号的位置发送变化，我们一个一个的分析：

• 2 号的后面没有影响，所以 2 号的后面依旧是 3 号；
• 5 号插到了 4 号的后面，所以 5 号的后面将会是原本 4 号后面的人，所以 5 号的后面为 2 号；
• 4 号的后面插进了一个 5 号，所以 4 号的后面变为 5 号。

所以整个链表变为：

所以用代码实现是这样：

这时，2 号同学离开了队伍，那么又会发送什么？

那么链表会变为：

• 5 号的后面原本是 2 号，但是 2 号离开了，2 号原本的后面是 3 号，所以 5 号的后面变为了 3 号。

所以变为：

改进：

我们可以用结构体减少内存。

原链表为：

浪费了很多的空间。

我们可以使用结构体：