AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 826. 单链表_Java    原题链接    简单

作者: 作者的头像   zning ,  2019-09-22 15:28:32 ,  阅读 899


9


5

链表

为什么使用数组来模拟链表

如果数据规模很大, 一个一个的new操作太慢了, 会超时, 使用数组会大大加快速度

单链表

数组模拟单链表

数组表示单链表.png

题目826

代码
import java.io.*;
import java.util.Scanner;

public class Main {
    private static int N = 100010;  // 数据规模为 10w

    private static int head;                // 表示头结点的下标
    private static int[] e = new int[N];    // 表示结点 i的值
    private static int[] ne = new int[N];   // 表示结点 i的 next指针是多少
    private static int idx;                 // 表示存储当前结点已经使用结点的下一个结点

    // 初始化数据
    private static void init() {
        head = -1;  // 没有头结点
        idx = 0;    // 没有存入数据
    }

    // 将 val插到头结点
    private static void addToHead(int val) {
        e[idx] = val;   // 赋值
        ne[idx] = head; // 插入之前头结点的前面
        head = idx;     // 更新头结点信息
        idx++;          // idx向右移动
    }

    // 将下标是 k的点后面的点删掉
    private static void remove(int k) {
        ne[k] = ne[ne[k]];  // 让下标为 k的结点指向 下个结点的下个结点
    }

    // 将 val插入下标为 k的点的后面
    private static void add(int k, int val) {
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }

    // 程序入口
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());

        init();     // 初始化操作

        // 进行 m次操作
        while (m-- > 0) {
            String[] s = reader.readLine().split(" ");

            if (s[0].equals("H")) {  // 插入头结点操作, 不能使用 ==, 要使用 equals()

                int val = Integer.parseInt(s[1]);
                addToHead(val);
            } else if (s[0].equals("I")) {   // 普通插入操作
                int k = Integer.parseInt(s[1]);
                int val = Integer.parseInt(s[2]);
                add(k - 1, val);    // 第 k个结点的下标为 k-1, 所以插入到下标为 k-1结点的后面
            } else {    // s[0] == "D", 删除操作
                int k = Integer.parseInt(s[1]);

                if (k == 0) {  // 题意: k = 0, 删除头结点
                    head = ne[head];
                } else
                    remove(k - 1);  // 第 k个结点的下标为 k-1, 所以是删除到下标为 k-1后面的后面
            }
        }

        // 打印输出
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

3 评论


用户头像
1641685571@qq.com   2个月前     回复

是不是用例更新了,用你的代码跑不通过呀


用户头像
潇湘夜雨   2019-12-19 09:36     回复

java的代码真是多的离谱儿=。=

用户头像
Susu   2020-01-27 13:45     回复

Java有时候写起来挺麻烦的,一堆static变量先敲在前面,图那边特别麻烦,一排static变量

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息