关于单链表问题
转载于一个大佬的完美解释https://www.acwing.com/solution/content/93739/
为什么不用课本上的单链表定义
为什么不用课本上学的结构体来构造链表？？
学过数据结构课的人，对链表的第一反应就是：
链表由节点构成，每个节点保存了 值 和 下一个元素的位置 这两个信息。节点的表示形式如下：
class Node{
public:
int val;
Node* next;
};
//新建 结点
Node* node = new Node();
node->val = x
这样构造出链表节点的是一个好方法，也是许多人一开始就学到的。
看一下创建新节点的代码的第一行：
Node* node = new Node();，中间有一个 new 关键字来为新对象分配空间。
new的底层涉及内存分配，调用构造函数，指针转换等多种复杂且费时的操作。一秒大概能new1w次左右。
在平时的工程代码中，不会涉及上万次的new操作，所以这种结构是一种 见代码知意 的好结构。
但是在算法比赛中，经常碰到操作在10w级别的链表操作，如果使用结构体这种操作，是无法在算法规定时间完成的。
所以，在算法比赛这种有严格的时间要求的环境中，不能频繁使用new操作。也就不能使用结构体来实现数组。
第 k 个插入的元素在哪里？
1.删除第 k 个插入的数后面的数
2.在第 k 个插入的数后插入一个数
在链表中删除指针指向的元素的后一个元素，或者在指针指向的某个元素后面插入一个新元素是很容易实现的。所以，只要弄明白第 k 个插入的数的指针在哪里，这两个问题就很容易解决。
来分析一下插入操作：
链表为空的时候：idx 的值为 0,
插入第一个元素 a 后：e[0] = a, idx 的值变为 1，
插入第二个元素 b 后：e[1] = b, idx 的值变为 2,
插入第三个元素 c 后：e[2] = c, idx 的值变为 3，
所以： 第 k 个出入元素的索引值 k - 1。
在看一下伴随着删除操作的插入：
链表为空的时候：idx 的值为 0,
插入第一个元素 a 后：e[0] = a, idx 的值变为 1，
插入第二个元素 b 后：e[1] = b, idx 的值变为 2,
删除第一个插入的元素 a：head 变为 1， idx 不变，依旧为 2。
删除第二个插入的元素 b：head 变为 2， idx 不变，依旧为 2。
插入第三个元素 c 后：e[2] = c, idx 的值变为 3。
所以删除操作并不改变第 k 个插入元素的索引。
故第 k 个元素的索引一定是 k - 1。
算法思路跟课本上的一样 只不过课本上是结构体或者类存储 这里是使用数组
AC 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int m;
int head, e[N], ne[N], idx;
void init()
{
idx = 0, head = -1;
}
void add_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++;
}
void del_k(int k)
{
if(!k) head = ne[head];
else ne[k - 1] = ne[ne[k - 1]];
}
void add_to_k(int k, int x)
{
e[idx] = x, ne[idx] = ne[k - 1], ne[k - 1] = idx ++;
}
int main()
{
init();
cin >> m;
while(m --)
{
char op;
cin >> op;
if(op == 'H')
{
int x;
cin >> x;
add_head(x);
}
else if(op == 'D')
{
int k;
cin >> k;
del_k(k);
}
else
{
int k, x;
cin >> k >> x;
add_to_k(k, x);
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
return 0;
}
