AcWing 826. 单链表
原题链接
简单
作者:
栎
,
2021-05-09 09:49:21
,
所有人可见
,
阅读 219
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少 也就是第 i+1 个结点的数组下标
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
// -1 相当于动态链表里面的空NULL
head = -1;
// 数组下标从0开始
idx = 0;
}
// 将x插到头结点
void add_to_head(int x)
{
// idx = 0; ne[idx] = head = -1, 也就是ne[0] = -1; head = 0, idx ++ = 1;
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
// 将x插到下标是k的点后面
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();
while (m -- )
{
int k, x;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
// 先判断k是否 等于 0 即是否是头结点
if (!k) head = ne[head];
else remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
// 遍历输出链表
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
// 删除的时候 如果k = 0 代表删除头结点 直接改变head“指针”的指向即可
// k在我们的代码中表示的是数组的下标 但在题目中表示的是 元素是第几个数
比如有数组 1 2 3 4 5
元素2的下标是1 但它是第2个数
所以在进行删除或插入操作时 传递的参数为k - 1, 即第k个数的下标为k - 1