題目連結:https://www.acwing.com/problem/content/description/828/
時/空限制:1s / 64MB
題目描述
實作一個單連結清單,連結清單初始為空,支援三種操作:
(1) 向連結清單頭插入一個數;
(2) 删除第k個插入的數後面的數;
(3) 在第k個插入的數後插入一個數
現在要對該連結清單進行M次操作,進行完所有操作後,從頭到尾輸出整個連結清單。
注意:題目中第k個插入的數并不是指目前連結清單的第k個數。例如操作過程中一共插入了n個數,則按照插入的時間順序,這n個數依次為:第1個插入的數,第2個插入的數,…第n個插入的數。
輸入格式
第一行包含整數M,表示操作次數。
接下來M行,每行包含一個操作指令,操作指令可能為以下幾種:
(1) “H x”,表示向連結清單頭插入一個數x。
(2) “D k”,表示删除第k個輸入的數後面的數(當k為0時,表示删除頭結點)。
(3) “I k x”,表示在第k個輸入的數後面插入一個數x(此操作中k均大于0)。
輸出格式
共一行,将整個連結清單從頭到尾輸出。
資料範圍
1≤M≤100000
所有操作保證合法。
輸入樣例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 3 4
D 6
輸出樣例
解題思路
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct List {
int data, next;
List() {}
List(int data, int next) : data(data), next(next) {}
}list_[MAXN];
int cnt = 0, head = 0;
void Insert_Head(int x) {
list_[++cnt] = List(x, list_[head].next);
list_[head].next = cnt;
}
void Delete(int k) {
if (!k)
head = list_[head].next;
else list_[k].next = list_[list_[k].next].next;
}
void Insert(int k, int x) {
list_[++cnt] = List(x, list_[k].next);
list_[k].next = cnt;
}
int main() {
char op;
int n, k, x;
scanf("%d", &n);
while (n--) {
scanf(" %c", &op);
if (op != 'I') {
if (op != 'D') {
scanf("%d", &x);
Insert_Head(x);
}
else {
scanf("%d", &k);
Delete(k);
}
}
else {
scanf("%d%d", &k, &x);
Insert(k, x);
}
}
int p = list_[head].next;
while (p) {
printf("%d ", list_[p].data);
p = list_[p].next;
}
printf("\n");
return 0;
}