题目描述

模拟双链表的插入头尾和任意位置左右的节点，删除第k个节点

输入样例

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

算法1

(数组) $O(n)$

主要就是通过数组的形式来表示双链表

时间复杂度：$O(n)$

参考文献：y总

JAVA代码

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int idx;
    static int[] e = new int[N];
    static int[] l = new int[N];
    static int[] r = new int[N];
    // 0代表head 1代表tail
    static void init(){
        r[0] = 1;// 头的右节点指向1
        l[1] = 0;// 尾的左节点指向0
        idx = 2;// 0 1 已经占用  从2开始
    }

    // k后面拆入点x
    static void add(int k, int x){
        e[idx] = x;
        l[idx] = k; r[idx] = r[k];
        l[r[k]] = idx; r[k] = idx++;
    }
    // 删除k节点 
    // 有点疑问就是既然删除的是k节点 为什么是remove(k + 1) 这应该是删除k后面的节点把？？？
    // 求广大同胞解答一下,谢谢！
    static void remove(int k){
        r[l[k]] = r[k];// 将k节点的左节点的右指针指向k节点的右节点
        l[r[k]] = l[k];// 将k节点的右节点的左指针指向k节点的左节点
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        init();
        while (m-- > 0){
            int k,x;
            String op = scan.next();
            if ("R".equals(op)){
                x = scan.nextInt();
                add(l[1], x);// 在1的左节点的后面插入x
            }else if ("L".equals(op)){
                x = scan.nextInt();
                add(0, x);// 在0的后面插入x
            }else if ("D".equals(op)){
                k = scan.nextInt();
                remove(k + 1);// 输入的k是从1开始的 idx从0开始 所以是k-1 但是0 1被占了 从2开始的 k-1+2
            }else if ("IL".equals(op)){
                k = scan.nextInt();
                x = scan.nextInt();
                add(l[k + 1], x);// 输入的k是从1开始的 idx从0开始 所以是k-1 但是0 1被占了 从2开始的 k-1+2
            }else if ("IR".equals(op)){
                k = scan.nextInt();
                x = scan.nextInt();
                add(k + 1, x);
            }
        }
        for (int i = r[0]; i != 1; i = r[i])
            System.out.print(e[i] + " ");
    }
}