每次都去找第k个插入的节点会超时,我是用一个hash表将节点存储下来实现O(1)的查找
C++ 代码
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
struct node {
int val;
int time;
node* next;
node(int x) : val(x), next(NULL), time(0) {};
};
unordered_map<int, node*> map;
node* insert_head(int x, node* head, int time) {
if (time == 1) {
head->time = 1;
head->val = x;
}
else {
node* Node = new node(x);
Node->time = time;
Node->next = head;
head = Node;
}
map[time] = head;
return head;
}
node* insert_k(int x, int k, node* head, int time) {
node* tmp = map[k];
node* now = new node(x);
now->time = time;
now->next = tmp->next;
tmp->next = now;
map[time] = now;
return head;
}
node* delete_k(int k, node* head) {
if (k == 0) {
head = head->next;
return head;
}
node* tmp = map[k];
if (tmp->next != NULL) {
tmp->next = tmp->next->next;
}
return head;
}
int main() {
int M;
cin >> M;
int time = 1;
node* head = new node(0);
for (int i = 1; i <= M; i++) {
char type;
cin >> type;
if (type == 'D') {
int k;
cin >> k;
head = delete_k(k, head);
}
else if (type == 'H') {
int k;
cin >> k;
head = insert_head(k, head, time);
time++;
}
else {
int k, x;
cin >> k >> x;
head = insert_k(x, k, head, time);
time++;
}
}
node* t = head;
while (t != NULL) {
cout << t->val << " ";
t = t->next;
}
}