链表的尾插法
https://www.nowcoder.com/discuss/480877823167569920
代码详细分析:
1. c set基本操作 增hash.insert();删hash.erase();查hash.count()/hash.find()
2. c 实现单链表(尾插法)
h头指针;e[]链表值;ne[]下一个结点;idx数组下一位下标
尾插法:检查链表是否空,空则建立头结点;不空,则遍历到尾部,插入新结点
删除操作:检查链表是否空,空则无法删除;不空,检查头结点是否符合,若符合,删除,若不符合,用ne进行遍历,找到后,删除
#include<iostream>
#include<unordered_set>
using namespace std;
const int N = 1e5 + 10;
int l, r;
int n;
int h, ne[N], e[N], idx;
int len;
unordered_set<int> _hash;
void insert(int id)
{
// cout << _hash.count(id) << endl;
if(_hash.count(id) != 0 || id > l ||id > r) return ;
_hash.insert(id);
//链表尾插法
int i = h;
if(i == -1){
h = idx, e[idx] = id, ne[idx] = -1, idx ++;
len ++;
return ;
}
while(ne[i] != -1){
i = ne[i];
}
e[idx] = id, ne[i] = idx, ne[idx] = -1, idx ++;
len ++;
}
void pop_top(int num)
{
if(num > len) return ;
for(int i = 0; i < num; ++i)
_hash.erase(e[h]), h = ne[h];
len --;
}
void pop_id(int id)
{
if(_hash.count(id) == 0 || id < l || id > r) return ;
int i = h;
if(e[i] == id) {
h = ne[h];
len --;
return ;
}
while(ne[i] != -1){
if(e[ne[i]] == id) {
_hash.erase(e[ne[i]]);
ne[i] = ne[ne[i]];
break;
}
}
len --;
}
int main()
{
cin >> l >> r >> n;
h = -1;
for(int id = l; id <= r; ++id){
insert(id);
}
while(n --)
{
int op, a;
cin >> op >> a;
if(op == 1)
{
pop_top(a);
}
else if(op == 2)
{
pop_id(a);
}
else if(op == 3)
{
insert(a);
}
}
// for(int i = h; i != -1; i = e[i])
// cout << e[h];
cout << e[h] << e[ne[h]] << e[ne[ne[h]]] << e[ne[ne[ne[h]]]];
}