一道鬼畜的链表操作

题目给的插入和删除的位置……hhh，之鬼畜法，第一反应是结构体加编号然后遍历一遍

然后...所有函数莫名其妙多出来几十行，附赠若干报错信息

我不是那种持之以恒的人，我选择开摆：

掏出绝招BFS(baidu first search)：百度优先搜索

然鹅并没有这题（度娘不靠谱啊）

此处省略800字弯路，咱直接看结果：

作为一道链表题，它有数据范围了！！！（OHHHHHHH）

这说明什么！说明要开固定的东西了！！！

数组万岁！！！！！！！！！！

但但但但问题又双叒叕来了：怎么做？

废话不多上代码，原理就在下面解释：

#include<iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;
void init()
{
	head = -1;
	idx = 0;
}
void addToHead(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx;
	idx++;
}
void add(int k,int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}
void remove(int k)
{
	ne[k] = ne[ne[k]];
}
int main()
{
	int m,k,x;
	char op;
	init();
	cin >> m;
	while (m--)
	{
		cin >> op;
		if (op == 'H')
		{
			cin >> x;
			addToHead(x);
		}
		else if (op == 'D')
		{
			cin >> k;
			if (k == 0)
			{
				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] << ' ';
	}
	return 0;
}

e[]:存储数据的地方

ne[]:存储下一个节点的下标

head:头结点下标

idx:未使用的第一个节点的下标

简而言之，头结点的值：e[head]

对于e[i]而言，其下一个的下标为ne[i]

空节点下标为-1（对应NULL）

那么，这个东西怎么解决问题的呢？

每次用完新节点后，idx++，说明第k个插入的元素就是下标为k-1的那个元素（注意数组下标从0开始）

所以，问题就解决啦~~~