B3631 单向链表 題解

ShanCreeperPro · 2022-05-21 16:42:59 · 题解

B3631 单向链表 題解

管理员注：

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

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

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

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

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

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

我们假设初始排队顺序为：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 号。

所以变为：

改进：

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

原链表为：

浪费了很多的空间。

我们可以使用结构体：