AcWing 826. 单链表
原题链接
简单
作者:
偶尔也会翻身的咸鱼
,
2024-04-07 14:21:27
,
所有人可见
,
阅读 3
手写指针单链表
#include <bits/stdc++.h>
using namespace std;
struct mylist {
int val;
mylist *next;
mylist(): val(-1), next(nullptr) {}
mylist(int x): val(x), next(nullptr) {}
mylist(int x, mylist* y): val(x), next(y) {}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
map<int, mylist*> mp;
auto head = new mylist(-1);
int ord = 0;
mp[0] = head;
auto listDelet = [&](mylist* p) {
auto q = p->next;
if (q) {
p->next = q->next;
}
};
auto listInsert = [&](mylist* p, int x) {
auto q = new mylist(x, p->next);
p->next = q;
mp[++ord] = q;
};
int q;
cin >> q;
while (q--) {
string op;
int x, k;
cin >> op;
if (op == "H") {
cin >> x;
listInsert(mp[0], x);
} else if (op == "D") {
cin >> k;
listDelet(mp[k]);
} else {
cin >> k >> x;
listInsert(mp[k], x);
}
}
for (auto p = head->next; p; p = p->next) {
cout << p->val << " ";
}
return 0;
}
STL list
#include <bits/stdc++.h>
using namespace std;
struct mylist {
int val;
mylist *next;
mylist(): val(-1), next(nullptr) {}
mylist(int x): val(x), next(nullptr) {}
mylist(int x, mylist* y): val(x), next(y) {}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
map<int, list<int>::iterator> mp;
list<int> lk;
int ord = 0;
int q;
cin >> q;
while (q--) {
string op;
int x, k;
cin >> op;
if (op == "H") {
cin >> x;
lk.push_front(x);
mp[++ord] = lk.begin();
} else if (op == "D") {
cin >> k;
if (k == 0) {
lk.erase(lk.begin());
}
else lk.erase(next(mp[k]));
} else {
cin >> k >> x;
mp[++ord] = lk.insert(next(mp[k]), x);
}
}
for (auto x: lk) {
cout << x << " ";
}
return 0;
}