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