双链表(参照acwing的yxc)

实现一个双链表双链表初始为空支持 5 种操作在最左侧插入一个数在最右侧插入一个数将第 k 个插入的数删除在第 k 个插入的数左侧插入一个数在第 k 个插入的数右侧插入一个数现在要对该链表进行 M 次操作进行完所有操作后从左到右输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数则按照插入的时间顺序这 n 个数依次为第 1 个插入的数第 2 个插入的数…第 n 个插入的数。输入格式第一行包含整数 M表示操作次数。接下来 M 行每行包含一个操作命令操作命令可能为以下几种L x表示在链表的最左端插入数 x。R x表示在链表的最右端插入数 x。D k表示将第 k 个插入的数删除。IL k x表示在第 k 个插入的数左侧插入一个数。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代码import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { //qq static int N100010; static int head-1;//头指针 static int tear-1;//尾指针 static int id0;//下一个可用节点下标 static int e[]new int[N];//存的是结点的值 static int ne[]new int[N];//存的是下一个结点的指针 static int fro[]new int[N];//存的是上一个结点的指针 public static void main(String[] args) throws IOException{ BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); // L x表示在链表的最左端插入数 x // R x表示在链表的最右端插入数 x // D k表示将第 k个插入的数删除。 // IL k x表示在第 k个插入的数左侧插入一个数。 // IR k x表示在第 k个插入的数右侧插入一个数。 int mInteger.parseInt(br.readLine()); for (int i 0; i m; i) { String t[]br.readLine().split( ); if(t.length2){ if(t[0].equals(L)){ int xInteger.parseInt(t[1]); addLeft(x); }else if(t[0].equals(R)){ int xInteger.parseInt(t[1]); addRight(x); }else if(t[0].equals(D)){ int kInteger.parseInt(t[1]); del(k); } }else{ if(t[0].equals(IL)){ int kInteger.parseInt(t[1]); int xInteger.parseInt(t[2]); addL(k,x); }else if(t[0].equals(IR)){ int kInteger.parseInt(t[1]); int xInteger.parseInt(t[2]); addR(k,x); } } } for(int ihead;i!-1;ine[i]){ System.out.print(e[i] ); } } static void addLeft(int x){//最左插入 if(head-1){ e[id]x; ne[id]-1; fro[id]-1; headid; tearid; return; } e[id]x; ne[id]head; fro[id]-1; fro[head]id;//注意加上 headid; } static void addRight(int x){//最右插入 if(tear-1){//空表 headid; ne[id]-1; e[id]x; fro[id]-1; headid; tearid;//注意加上 return; } e[id]x; fro[id]tear; ne[tear]id; ne[id]-1; tearid; } static void del(int k){//删除第 k个插入的数 k--; if(khead){//删头结点 if(ne[k]-1){//是头也是尾 head-1; tear-1; }else{ headne[k]; fro[ne[k]]-1; } }else if(ne[k]-1){//删尾结点 ne[fro[k]]-1; tearfro[k]; }else{ fro[ne[k]]fro[k]; ne[fro[k]]ne[k]; } } static void addL(int k,int x){//在第 k个插入的数左侧插入一个数 k--; e[id]x; ne[id]k; if(khead){ addLeft(x); // headid; // fro[id]-1; // fro[k]id; }else{ fro[id]fro[k]; ne[fro[k]]id; fro[k]id; id; } } static void addR(int k,int x){//在第 k个插入的数右侧插入一个数 k--; e[id]x; if(ne[k]-1){ addRight(x); // ne[k]id; // fro[id]k; // tearid; }else{ ne[id]ne[k]; fro[id]k; fro[ne[k]]id; ne[k]id; id; } } }