一、链表
1.1 单链表
package 链表;public class 单链表 {static int e[] = new int[11010]; // index号节点的value值（value）static int ne[] = new int[11010];// index号节点的下一个节点的index（nextNode）static int head=-1,idx=0; // 头节点的index，当前可用的最小indexpublic static void main(String[] args) {// TODO Auto-generated method stub// 遍历单链表for(int i=head;i!=-1;i = ne[i]) {System.out.print(e[i]);}}// 插入——链头static void add_to_head(int x) {e[idx] = x; ne[idx] = head; head = idx; idx++;}// 插入——第k个节点之后static void add_afterK(int k,int x) {e[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx++;}// 删除——第k个节点之后节点static void remove(int k,int x) {ne[k] = ne[ne[k]];}
}例题： B3631 单向链表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
import java.util.*;
public class Main {static int e[] = new int[11011];static int en[] = new int[11011];static int head = 0,idx = 1;public static void main(String[] args) {// TODO Auto-generated method stubScanner in = new Scanner(System.in);e[0] = 1; en[0] = -1;int q = in.nextInt();while(q--!=0) {int o = in.nextInt();if(o==1) {int x = in.nextInt();int y = in.nextInt();add(x,y);}else if(o==2) {int x = in.nextInt();int index = find_index(x);if(en[index]==-1) {System.out.print("0\n");}else {System.out.print(e[en[index]]+"\n");}}else {int x = in.nextInt();remove(x);}}}static void add(int x,int y) {x = find_index(x);e[idx] = y;en[idx] = en[x];en[x] = idx;idx++;}static void remove(int x) {x = find_index(x);en[x] = en[en[x]];}static int find_index(int x) {for(int i=head;i!=-1;i = en[i])if(e[i]==x)return i;return -1;}
}
这个代码会有三个数据超时，应该改成快读就行了。
1.12双向链表
package 链表;public class 双链表 {static int e[] = new int[11010]; // index号节点的value值（value）static int l[] = new int[11010];// index号节点的左边节点的indexstatic int r[] = new int[11010];// index号节点的右边节点的indexstatic int idx = 2;public static void main(String[] args) {// TODO Auto-generated method stub}// 初始化static void init() {r[0] = 1; l[1] = 0;}// K的右边插入xstatic void add_afterK(int k,int x) {e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;}// K的左边插入xstatic void add_beforeK(int k,int x) {add_afterK(l[k],x);}// 删除——第k个节点static void remove(int k) {r[l[k]] = r[k];l[r[k]] = l[k];}
}
