题目描述
实现一个双链表,双链表初始为空,支持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
输出样例:
8 7 7 3 2 9
注解可以看c++
思路
由于双链表思路和单链表差不多
可以链接转到单链表,进行理解
https://www.acwing.com/solution/content/32965/
java
import java.io.*;
public class Main{
static int m;
static int N = 100010;
static int[] e = new int[N], l = new int[N], r = new int[N];
static int idx;
public static void init(){
r[0] = 1;
l[1] = 0;
idx = 2;
}
public static void add(int k, int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
public static void remove(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
public static void main(String[] args) throws IOException{
init();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
m = Integer.parseInt(br.readLine());
while(m -- > 0){
int k, x;
String[] s = br.readLine().split(" ");
String opt = s[0];
if(opt.equals("L")){
x = Integer.parseInt(s[1]);
add(0, x);
}else if(opt.equals("R")){
x = Integer.parseInt(s[1]);
add(l[1], x);
}else if(opt.equals("D")){
k = Integer.parseInt(s[1]);
remove(k + 1);
}else if(opt.equals("IL")){
k = Integer.parseInt(s[1]);
x = Integer.parseInt(s[2]);
add(l[k + 1], x);
}else{
k = Integer.parseInt(s[1]);
x = Integer.parseInt(s[2]);
add(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]){
System.out.print(e[i] + " ");
}
}
}
python3
N = 100010
e = [0] * 100010
l = [0] * 100010
r = [0] * 100010
#初始化
r[0], l[1], idx = 1, 0, 2
def add(k, x):
global e, l, r, idx;
e[idx] = x
r[idx] = r[k]
l[idx] = k
l[r[k]] = idx
r[k] = idx
idx += 1
def remove(k):
r[l[k]] = r[k]
l[r[k]] = l[k]
def main():
global e, l, r, idx
m = int(input())
while(m):
m -= 1;
s = list(input().split(" "))
opt = s[0]
if(opt == "L"):
x = int(s[1])
add(0, x)
elif(opt == "R"):
x = int(s[1])
add(l[1], x)
elif(opt == "D"):
k = int(s[1])
remove(k + 1)
elif(opt == "IL"):
k = int(s[1])
x = int(s[2])
add(l[k + 1], x)
else:
k = int(s[1])
x = int(s[2])
add(k + 1, x)
i = r[0]
while(i != 1):
print(e[i], end=" ")
i = r[i]
main()
c++
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
//初始化
void init(){
//0表示左端点 1表示右端点 0 <-> 1
r[0] = 1, l[1] = 0;
idx = 2;
}
void add(int k, int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
void remove(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(){
int m;
cin >> m;
init();
while(m --){
string opt;
int k, x;
cin >> opt;
if(opt == "L"){
//(1) “L x”,表示在链表的最左端插入数x。
cin >> x;
add(0, x);
}
else if(opt == "R"){
//(2) “R x”,表示在链表的最右端插入数x。
cin >> x;
add(l[1], x);
}
else if(opt == "D"){
//(3) “D k”,表示将第k个插入的数删除。
cin >> k;
remove(k + 1); //idx从2开始, (k + 2) - 1 (k + 2)是真实的坐标位置 -1是从0(真实的是从2)开始
}
else if(opt == "IL"){
//(4) “IL k x”,表示在第k个插入的数左侧插入一个数。
cin >> k >> x;
add(l[k + 1], x);
}
else{
//(5) “IR k x”,表示在第k个插入的数右侧插入一个数。
cin >> k >> x;
add(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
cout << endl;
return 0;
}