双链表 AcWing 827. 双链表

原题链接

AcWing 827. 双链表

算法标签

链表

思路

插入节点k
若为在第 k 个插入的数右侧插入一个数 即函数add(k, x)需要
在第 k 个插入的数左侧插入一个数， 相当于add(l[k+1], x)
若在链表的最左端插入数 x 相当于add(0, x)
若在链表的最右端插入数 x 相当于add(l[1], x)
删除节点k

由于初始链表当前下标为2， 股灾操作过程中， 第k个位置实际传入下标为k+1

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
//l[N]存储元素左指针 r[N]存储元素右指针  
// head为头节点，初始化为0 tail为尾节点，初始化为1
// idx为链表初始最大节点下标 由于存在头节点与尾节点， 初始化为2
int e[N], l[N], r[N], idx=2;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
// 在节点k的右边插入一个数x
void add(int k, int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
void remove(int k){
	l[r[k]]=l[k];
    r[l[k]]=r[k];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m=read();
	r[0]=1, l[1]=0;
	while(m--){
	    char op[2];
	    scanf("%s", op);
	    if(op[0]=='L'){
	        int x=read();
	        add(0, x);
	    }else if(op[0]=='R'){
	        int x=read();
	        add(l[1], x);
	    }else if(op[0]=='D'){
	        int k=read();
	        remove(k+1);
	    }else if(op[0]=='I'&&op[1]=='L'){
	        int k=read(), x=read();
	        add(l[k+1], x);
	    }else{
	        int k=read(), x=read();
	        add(k+1, x);
	    }
	}
	for(int i=r[0]; i!=1; i=r[i]){
	    printf("%lld ", e[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

模板

// 插入
void add(int k, int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
// 删除
void remove(int k){
	l[r[k]]=l[k];
    r[l[k]]=r[k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13