java模板
//head头指针,e[]存储节点的值,idx表示当前要操作的节点的索引
//ne数组存放的是next指针,也就是下一个节点的索引,相当于向后走一步
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}
//在k后删除值
void remove_k(int k)
{
ne[k] = ne[ne[k]];
}
//在k后添加值
void insert(int k,int x)
{
e[idx] = x; //赋值
ne[idx] = ne[k]; //替换k
ne[k] = idx; //指向idx
idx++; //后移
}
java代码
import java.util.Scanner;
public class Main{
private static int N = 100010;
private static int head, idx; //head表示头节点 idx表示当前要操作的节点的索引
private static int[] e = new int[N]; //e数组存放的是节点的值
private static int[] ne = new int[N]; //ne数组存放的是next指针,也就是下一个节点的索引
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int m = in.nextInt();
init();
while(m-- > 0){
String a = in.next();
if(a.equals("H")){
int x = in.nextInt();
addToHead(x);
}else if(a.equals("D")){
int k = in.nextInt();
if(k == 0){ //k = 0时,k = -1,就会数组越界,所以应该在在头节点后删除值
remove_Head();
}else{
remove_k(k-1); //注意第k个数的索引是k - 1
}
}else if(a.equals("I")){
int k = in.nextInt();
int x = in.nextInt();
insert(k-1,x);
}
}
for(int i = head; i != -1;i = ne[i]) System.out.print(e[i] + " ");
}
private static void init(){ //初始化
head = -1;
idx = 0;
}
private static void addToHead(int x){ //在头节点后添加值
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
private static void remove_Head(){ //在头节点后删除值
head = ne[head];
}
private static void remove_k(int k){ //在k后删除值
ne[k] = ne[ne[k]];
}
private static void insert(int k,int x){ //在k后添加值
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
}
注意点
1:head = ne[k]
2:注意第k个数的索引是k - 1
3:在删除节点时,注意当k等于0时,k-1 = -1,会出现数组越界,此时应该在头节点后删除值