题目描述

单链表

JAVA 代码

import java.util.*;
class Main{
    static final int N = 100010;
    static int [] e, ne;
    static int idx,head;

    //初始化. 
    static void init(){
        head = -1;
        idx = 0;
        e = new int[N];
        ne = new int[N];
    }
    //下一个节点的下一个
    static void remove(int k){
        ne[k]=ne[ne[k]];
    }

    //新增 第k个节点
    static void add(int k,int x){
        e[idx] = x;
        //当前节点下一个为 k的下一个节点
        ne[idx] = ne[k];
        //k的下一个节点为 当前节点.
        ne[k] = idx;
        idx++;
    }
    static void add_to_head(int x){
        e[idx] = x;
        ne[idx] = head;
        head = idx;
        idx++;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        init();
        while (m-- > 0) {
            String str = sc.next();
            if (str.equals("H")) {
                int x = sc.nextInt();
                add_to_head(x);
            } else if (str.equals("I")) {
                int k = sc.nextInt();
                int x = sc.nextInt();
                add(k - 1, x);
            } else if (str.equals("D")) {
                int k = sc.nextInt();
                if (k == 0)
                    head = ne[head];
                else
                    remove(k - 1);
            }
        }


        int i = head;
        while (i != -1) {
            System.out.print(e[i] + " ");
            i = ne[i];
        }
    }
}