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

2023-11-30 12:44

本文主要是介绍算法通关村第一关—青铜挑战—用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指向插入位置前一个结点的nextnewNode.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); // 获取该链表的总长度sizeint i = 1;while (i < size - 1) { // 找到倒数第二个结点i++;newNode = newNode.next;}newNode.next = null; // 将倒数第二个结点的next指向nullreturn 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;}
}

这篇关于算法通关村第一关—青铜挑战—用Java基本实现各种链表操作的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/437079

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法