算法通关村第一关—青铜挑战—用Java基本实现各种链表操作

文章目录

  • 第一关—链表【青铜挑战】
    • 1.1 单链表的概念
    • 1.2 链表的相关概念
    • 1.3 创建链表 - Java实现
    • 1.4 链表的增删改查
      • 1.4.1 遍历单链表 - 求单链表长度
      • 1.4.2 链表插入 - 三种位置插入
        • （1）在链表的表头插入
        • （2）在链表的中间插入
        • （3）在链表的结尾插入
        • （4）在链表的所有位置插入[总结]⭐
      • 1.4.3 链表删除 - 三种位置删除
        • （1）删除链表的表头结点
        • （2）删除链表的最后一个结点
        • （3）删除链表的中间结点
        • （4）删除链表的任一位置[总结]⭐

第一关—链表【青铜挑战】

1.1 单链表的概念

  • 单向链表就像一个铁链一样，元素之间互相连接，包含多个结点，每个结点**只有一个**指向后继元素的next指针，并且最后一个元素的next指向null

在这里插入图片描述

小练：以下两张图，是否满足单链表的要求

在这里插入图片描述
在这里插入图片描述
解析：

第一张图满足单链表的要求，第二张图不满足要求，因为c1它有两个后继结点a5和b4，单链表的核心是一个结点只能有一个后继，但是不代表一个结点只能有一个被指向（如c1可以被a2和b3指向）

注意：做题的时候注意比较的是值还是结点，有时可能两个结点的值是相等的，但并不是同一个结点，例如下图，有两个结点的值都是1，但并不是同一个结点

在这里插入图片描述

1.2 链表的相关概念

节点和头节点

在链表中，每个点都由值和指向下一个节点的地址组成独立的单元，成为一个结点，有时也称为节点，含义都是一样的

对于单链表而言，如果知道了第一个元素，就可以遍历访问整个链表，因此第一个节点最重要，一般称为头节点

虚拟结点

虚拟结点就是一个dummyNode，其next指针指向head头部，也就是dummyNode.next = head

因此，如果我们在算法里使用了虚拟结点，则要注意，如果要获得head结点，或者从方法里返回的时候，则应使用dummyNode.next

另外，dummyNode的val不会被使用，初始化为0或者-1等都是可以的，既然值不会被使用，那么我们就会有疑问？虚拟结点有啥用呢？简单来说，就是为了方便我们处理头结点，否则我们需要在代码里单独处理头结点【首部结点】的问题
在这里插入图片描述

1.3 创建链表 - Java实现

我们首先要理解JVM是怎么构建出链表，JVM里面有栈区和堆区，堆区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象

在这里插入图片描述

/**
 * @Author Zan
 * @Date 2023/11/29 14:46
 * @Description : 传入一个数组，将其转换成单链表
 */
public class BasicLink {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        Node head = initLinkedList(a);
        System.out.println(head);
    }

    private static Node initLinkedList(int[] array) {
        Node head = null, current = null;
        for (int i = 0; i < array.length; i++) {
            Node newNode = new Node(array[i]);
            if (i == 0) { // 头节点
                // 由于head = current，因此当current在变化的时候，head也在变化
                head = newNode;
//                newNode = new Node(array[i]); // 如果在此将newNode重新定义，指向的是不同的堆数据，因此head就只是一个Node普通对象，单节点的链表
                current = newNode;
            } else { // 后面的节点
                current.next = newNode;
                current = newNode;
            }
        }
        return head;
    }


    static class Node {
        public int x;
        public Node next;

        public Node(int x) {
            this.x = x;
            next = null;
        }
    }
}

在这里插入图片描述

我们可以看到初始化链表的时候，head和current指向的是同一个对象，也就是指向堆中的同一个数据，因此当控制current.next = newNode 的时候，其实就是控制堆中的数据指向谁，next指向下一条数据，而head跟current一样指向的是同一个对象，因此就可以跟随其变化

在这里插入图片描述
最后得到head如下图所示 - 单链表的形式

在这里插入图片描述

1.4 链表的增删改查

  • 对于单链表而言，不管进行什么操作，一定都是从头开始逐个向后开始访问，所以操作之后是否还能够找到表头非常重要

1.4.1 遍历单链表 - 求单链表长度

/**
 * 遍历链表，获取链表的长度
 * @param head 头节点
 * @return
 */
public static int getListLength(Node head) { // 传入头节点
    int length = 0;
    Node node = head;
    while (node != null) { // 一个一个节点遍历
        length++;
        node = node.next;
    }
    return length;
}

1.4.2 链表插入 - 三种位置插入

  • 单链表的插入，和数组的插入一样，过程不复杂。但是单链表的插入操作需要考虑三种情况：首部、中部和尾部
（1）在链表的表头插入
  1. 创建新结点newNode
  2. 新结点的next = head，即newNode.next = head
  3. 头head指向新的链表，即head = newNode

在这里插入图片描述

/**
 * 在链表的表头插入
 * @param head 原链表
 * @param nodeInsert 要插入表头的结点元素
 * @return
 */
public static Node insertNodeByHead(Node head, Node nodeInsert) {
    nodeInsert.next = head;
    head = nodeInsert;
    return head;
}

在这里插入图片描述

（2）在链表的中间插入
  1. 循环找到要插入位置position的前一个结点（位置从1开始）
  2. 将插入结点的next指向前一个结点的next，即nodeInsert.next = newNode.next
  3. 将前一个结点的next指向插入结点，即newNode.next = nodeInsert
  • 注意：我们不能先将前一个结点的next指向插入结点，这是因为每个结点都只有一个next，因此如果先将前一个结点的next指向插入结点，那么15->7这一条线就断掉了，也就导致后面的7、40将会找不到，断开

在这里插入图片描述

/**
 * 在链表的中间位置插入
 * @param head 原链表的头结点
 * @param nodeInsert 要插入的结点
 * @param position 要插入的位置，从1开始
 * @return
 */
public static Node insertNodeByPosition(Node head, Node nodeInsert, int position) {
    Node newNode = head; // 不对原链表进行操作，用新链表指向堆中的同一个元素，进行堆中的操作
    int i = 1;
    while (i < position - 1) { // 要在中间位置插入，因此要获取插入位置的前一个结点，这样子才能将next连接起来
        newNode = newNode.next;
        i++;
    }
    nodeInsert.next = newNode.next; // 将要插入的结点的next指向插入位置前一个结点的next
    newNode.next = nodeInsert; // 将插入位置前一个结点的next指向要插入的结点
    return head;
}

在这里插入图片描述

（3）在链表的结尾插入
  1. 获取原链表总共有多少个元素
  2. 循环遍历找到最后一个结点
  3. 将最后一个结点的next指向新结点

在这里插入图片描述

/**
 * 在链表的结尾插入
 * @param head 原链表的头结点
 * @param nodeInsert 要插入的结点
 * @return
 */
public static Node insertByEnd(Node head, Node nodeInsert) {
    Node newNode = head;
    int nodeLength = getListLength(newNode); // 获取到原链表的元素个数
    int i = 1;
    while (i < nodeLength) { // 循环遍历找到最后一个结点
        newNode = newNode.next;
        i++;
    }
    newNode.next = nodeInsert; // 将最后一个结点的next指向新结点
    return head;
}

在这里插入图片描述

（4）在链表的所有位置插入[总结]⭐
/**
 * 链表的插入（所有情况，表头、中间、结尾）
 *
 * @param head 原链表
 * @param nodeInsert 插入的结点
 * @param position 插入的位置，从1开始
 * @return
 */
public static Node insertNode(Node head, Node nodeInsert, int position) {
    // head原链表中没有数据，插入的结点就是链表的头结点
    if (head == null) {
        return nodeInsert;
    }

    // 获取存放元素个数 - 进行校验(position在[1, size]之间)
    int size = getListLength(head);
    if (position > size + 1 || position < 1) {
        System.out.println("位置参数越界");
        return head;
    }

    // 表头插入
    if (position == 1) {
        nodeInsert.next = head;
        head = nodeInsert;
        return head;
    }

    // 中间插入和结尾插入
    Node newNode = head;
    int count = 1;
    while (count < position - 1) {
        count++;
        newNode = newNode.next;
    }
    nodeInsert.next = newNode.next;
    newNode.next = nodeInsert;

    return head;
}

1.4.3 链表删除 - 三种位置删除

  • 删除同样分为删除头部元素、删除中间元素和删除尾部元素
（1）删除链表的表头结点

将head表头向前移动一次之后，原先的结点就变成了不可达，会被JVM回收掉

在这里插入图片描述

/**
 * 删除表头结点
 * @param head 原链表
 * @return
 */
public static Node deleteByHead(Node head) {
    head = head.next;
    return head;
}

在这里插入图片描述

（2）删除链表的最后一个结点
  1. 获取该链表的总长度size
  2. 找到倒数第二个结点
  3. 将倒数第二个结点的next指向null，即newNode.next = null

在这里插入图片描述

/**
 * 删除最后一个结点
 * @param head 原链表
 * @return
 */
public static Node deleteByEnd(Node head) {
    Node newNode = head;
    int size = getListLength(head); // 获取该链表的总长度size
    int i = 1;
    while (i < size - 1) { // 找到倒数第二个结点
        i++;
        newNode = newNode.next;
    }
    newNode.next = null; // 将倒数第二个结点的next指向null
    return head;
}

在这里插入图片描述

（3）删除链表的中间结点
  1. 找到要删除结点的前一个结点
  2. 将前一个结点的next指向下下个结点，即newNode.next = newNode.next.next

在这里插入图片描述

/**
 * 删除中间结点
 * @param head 原链表
 * @return
 */
public static Node deleteByPosition(Node head, int position) {
    Node newNode = head;
    int i = 1;
    while (i < position - 1) {
        i++;
        newNode = newNode.next;
    }
    newNode.next = newNode.next.next;
    return head;
}

在这里插入图片描述

（4）删除链表的任一位置[总结]⭐
/**
 * 删除结点（三种情况，表头、中间、最后一位结点）
 * @param head 原链表
 * @return
 */
public static Node deleteNode(Node head, int position) {
    // 如果没有结点，说明无法删除，直接返回null即可
    if (head == null) {
        return null;
    }

    //校验
    int size = getListLength(head);
    if (position > size || position < 1) { // 这里不是size+1，而插入是size+1，因为插入可以插入到最后一位（未知的最后一位），而删除必须要是已知的，不能是未知的越界
        System.out.println("输入的参数有误");
        return head;
    }

    if (position == 1) { // 删除头节点
        return head.next;
    } else { // 删除中间结点或者最后一个结点
        Node newNode = head;
        int count = 1;
        while (count < position - 1) {
            count++;
            newNode = newNode.next;
        }
        newNode.next = newNode.next.next;
        return head;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/201943.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Testlink 1.9.20+phpstudy_pro安装遇到的问题

Testlink 1.9.20+phpstudy_pro安装遇到的问题

phpstudy_pro启动了Apache2.4.39和Mysql5.7.26,php的版本是7.3.4zai。 安装Testlink 1.9.19时没有数据库的问题&#xff0c;安装Testlink 1.9.20时遇到了数据库问题&#xff0c;如下图所示&#xff1a; 网上搜索“Failed!Mysql Database cannnot be used”&#xff0c;给出的…
阅读更多...
香港身份、香港永居身份、香港护照区别，三种证件之间是什么关系？

香港身份、香港永居身份、香港护照区别，三种证件之间是什么关系？

香港身份、香港永居身份、香港护照区别&#xff0c;三种证件之间是什么关系&#xff1f; 在港“通常性”住满7年之后&#xff0c;可以申请永居身份&#xff01; 香港身份&#xff1a;也可以称之为临时身份&#xff0c;无论通过香港优才计划、高才通计划、专才计划或者留学拿身份…
阅读更多...
ANN人工神经网络：从基础认知到现实理解

ANN人工神经网络：从基础认知到现实理解

什么是神经网络&#xff1f; 神经网络的再认知 前面我们了解过&#xff0c;人工神经网络&#xff08;Artificial Neural Network&#xff0c;ANN&#xff09;是人类为了模仿人大脑的神经网络结构创建出来的一种计算机系统结构。但如果仔细深入到神经网络当中&#xff0c;会慢…
阅读更多...
Deep Learning（wu--84）

Deep Learning（wu--84）

文章目录 2偏差和方差正则化梯度消失\爆炸权重初始化导数计算梯度检验OptimizationMini-Batch 梯度下降法指数加权平均偏差修正RMSpropAdam学习率衰减局部最优问题 调参BNsoftmax framework 2 偏差和方差 唔&#xff0c;这部分在机器学习里讲的更好点 训练集误差大&#xff…
阅读更多...
修改YOLOv5的模型结构第三弹

修改YOLOv5的模型结构第三弹

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制&#x1f680; 文章来源&#xff1a;K同学的学习圈子 文章目录 任务任务拆解 开始修改C2模块修改yolo.py修改模型配置文件 模型训练 上次已…
阅读更多...
点击元素以外的事件监听

点击元素以外的事件监听

在项目中&#xff0c;我们经常会遇到需要监听目标元素以外的区域被点击或鼠标移入移出等需求。 例如下面我们有一个表格里面嵌套表单的组件 我希望点击n行的时候&#xff0c;n行的元素变成表单元素进行输入或者选择&#xff0c; 当我点击其他其他区域n行又会恢复成数据展示…
阅读更多...
web和微信小程序设置placeholder样式

web和微信小程序设置placeholder样式

文章目录 一、场景二、web2.1、概念2.2、用法2.3、样式 三、小程序四、最后 一、场景 在页面布局时经常会用到input输入框&#xff0c;有时为了提示用户输入正确的信息&#xff0c;需要用placeholder属性加以说明。 二、web 2.1、概念 placeholder 是HTML5 中新增的一个属性…
阅读更多...
拼图 游戏

拼图 游戏

运行出的游戏界面如下&#xff1a;按住A不松开&#xff0c;显示完整图片&#xff1b;松开A显示随机打乱的图片 User类 package domain;/*** ClassName: User* Author: Kox* Data: 2023/2/2* Sketch:*/ public class User {private String username;private String password;p…
阅读更多...
C# WPF上位机开发（倒计时软件）

C# WPF上位机开发（倒计时软件）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 生活当中&#xff0c;我们经常会遇到倒计时的场景&#xff0c;比如体育运动的时候、考试的时候等等。正好最近我们学习了c# wpf开发&#xff0c;完…
阅读更多...
Azure Machine Learning - 创建Azure AI搜索索引

Azure Machine Learning - 创建Azure AI搜索索引

目录 一、先决条件检查空间 二、创建和加载索引启动向导连接到 数据源跳过认知技能配置配置索引配置索引器 三、监视索引器进度四、检查搜索索引结果五、添加或更改字段六、使用搜索浏览器查询七、运行更多示例查询八、清理资源 在本文中&#xff0c;你将使用导入数据向导和由虚…
阅读更多...
MATLAB实战 | APP设计

MATLAB实战 | APP设计

01、应用实战 【例1】生成一个用于观察视点仰角和坐标轴着色方式对三维图形显示效果影响的App&#xff0c;界面如图1所示。界面右上部的列表框用于选择绘图数据、切换按钮组用于选择绘图方法&#xff0c;中间的旋钮用于设置视点方位角和仰角&#xff0c;右下部的分档旋钮用于设…
阅读更多...
计算机毕业设计 基于协同推荐的白酒销售管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 基于协同推荐的白酒销售管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
vivado综合分析与收敛技巧2

vivado综合分析与收敛技巧2

1、分解深层存储器配置 &#xff0c; 实现功耗与性能平衡 在深层存储器配置中 &#xff0c; 可使用综合属性 RAM_DECOMP 实现更好的存储器分解并降低功耗。此属性可在 RTL 中设置。将RAM_DECOMP 属性应用于存储器时 &#xff0c; 存储器是在较宽的原语配置中设置的 &#x…
阅读更多...
【开源视频联动物联网平台】流媒体传输协议HLS，FLV的功能和特点

【开源视频联动物联网平台】流媒体传输协议HLS，FLV的功能和特点

HLS&#xff08;HTTP Live Streaming&#xff09;和FLV&#xff08;Flash Video&#xff09;都是用于视频流传输的协议或容器格式&#xff0c;但它们在某些方面有着显著的区别和特点。 HLS是一种由苹果公司开发的用于流媒体传输的协议&#xff0c;而FLV则是Adobe公司开发的用于…
阅读更多...
数据挖掘之时间序列分析

数据挖掘之时间序列分析

一、 概念 时间序列&#xff08;Time Series&#xff09; 时间序列是指同一统计指标的数值按其发生的时间先后顺序排列而成的数列&#xff08;是均匀时间间隔上的观测值序列&#xff09;。 时间序列分析的主要目的是根据已有的历史数据对未来进行预测。 时间序列分析主要包…
阅读更多...
详解前后端交互时PO,DTO,VO模型类的应用场景

详解前后端交互时PO,DTO,VO模型类的应用场景

前后端交互时的数据传输模型 前后端交互流程 前后端交互的流程: 前端与后端开发人员之间主要依据接口进行开发 前端通过Http协议请求后端服务提供的接口后端服务的控制层Controller接收前端的请求Contorller层调用Service层进行业务处理Service层调用Dao持久层对数据持久化 …
阅读更多...
2023长三角（芜湖）人工智能数字生态峰会暨视觉算法大赛颁奖典礼邀您一同参与！

2023长三角（芜湖）人工智能数字生态峰会暨视觉算法大赛颁奖典礼邀您一同参与！

时光荏苒&#xff0c;科技飞速发展&#xff0c;人工智能正在以令人瞩目的速度改变着我们的生活。在这个数字科技的新时代&#xff0c;为促进长三角地区人工智能产业的蓬勃发展&#xff0c;助推数字经济的繁荣&#xff0c;2023长三角&#xff08;芜湖&#xff09;人工智能数字生…
阅读更多...
BEVFormer【人工智能】

BEVFormer【人工智能】

BEVFormer 是一篇今年中稿 ECCV 2022 的论文&#xff0c;其中提出了一种纯视觉&#xff08;camera&#xff09;感知任务的算法模型&#xff0c;用于实现3D目标检测和地图分割任务。该算法通过提取环视相机&#xff08;Bird’s Eye View Camera&#xff09;采集到的图像特征&…
阅读更多...
[论文阅读]CT3D——逐通道transformer改进3D目标检测

[论文阅读]CT3D——逐通道transformer改进3D目标检测

CT3D 论文网址&#xff1a;CT3D 论文代码&#xff1a;CT3D 简读论文 本篇论文提出了一个新的两阶段3D目标检测框架CT3D,主要的创新点和方法总结如下: 创新点: (1) 提出了一种通道注意力解码模块,可以进行全局和局部通道聚合,生成更有效的解码权重。 (2) 提出了建议到点嵌…
阅读更多...
Node.js下载安装教程

Node.js下载安装教程

一、下载安装包 1、百度网盘自提链接&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1Bbw895MtUgjlfZylPHCCxw 提取码&#xff1a;x89v 2、进入官网下载 https://nodejs.org/zh-cn/download/ 选择对应版本&#xff0c;我这里选的windows64位版本 二、安装程序 1、…
阅读更多...
最新文章

Copyright @ 2022~2023