当前位置: 首页 > news >正文

【剧前爆米花--爪哇岛寻宝】Java实现无头单向非循环链表和无头双向链表与相关题目

作者:困了电视剧

专栏:《数据结构--Java》

文章分布:这是关于数据结构链表的文章,包含了自己的无头单向非循环链表和无头双向链表实现简单实现,和相关题目,想对你有所帮助。

 

 

目录

无头单向非循环链表实现

无头双向链表实现

链表的相关题目

移除链表元素

反转一个单链表

链表的中间结点

链表中倒数第k个结点


无头单向非循环链表实现

public class SingleLinkedList {static class Node {public int val;//存储的数据public Node next;//存储下一个节点的地址//public Node(){}public Node (int val) {this.val = val;}}public Node head;public int size=0;//头插法public void addFirst(int data){Node node = new Node(data);node.next=head;head = node;size++;}//尾插法public void addLast(int data){Node node = new Node(data);if ( head==null ){head=node;return;}Node tmp=head;while ( tmp.next!=null ){tmp=tmp.next;}tmp.next=node;size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//先判断idx是否合法if ( index>size||index<0 ){return false;}if ( head==null ){return false;}Node node = new Node(data);Node cur=head;int cnt=0;while ( cnt!=index ){cur=cur.next;cnt ++;}node.next=cur.next;cur.next=node;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if ( head==null ){return false;}Node cur = head;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if ( head==null ){return;}if ( head.val==key ){head=head.next;return;}Node cur = head;while ( cur.next!=null ){if ( cur.next.val==key ){cur.next=cur.next.next;return;}cur=cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if ( head==null ){return;}Node pre=head;Node cur=head.next;while ( cur!=null ){if ( cur.val==key ){cur=cur.next;pre.next=cur;}else{pre=cur;cur=cur.next;}}if ( head.val==key ){head=head.next;}return;}//得到单链表的长度public int size(){return this.size;}public void display(){if ( head==null ){return;}Node cur=head;while ( cur!=null ){System.out.println(cur.val+" ");}}public void clear(){head=null;}
}

无头双向链表实现

public class MyLinkedList {//内部类构造一个链表数据结构static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(){}public ListNode(int val){this.val=val;}}private ListNode first;private ListNode last;private int size=0;MyLinkedList(){}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{node.next=first;first.prev=node;first=node;}size++;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{last.next=node;node.prev=last;last=node;}size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//判断这个index是否合法if ( index<0 || index>size ){return false;}ListNode node=new ListNode(data);ListNode cur=first;for ( int i=0;i<index;i++ ){cur=cur.next;}if ( cur==first ){node.next=cur;cur.prev=node;first=node;}else if ( cur==last ){last.next=node;node.prev=last;last=node;}else{node.next=cur;node.prev=cur.prev;cur.prev.next=node;cur.prev=node;}return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=first;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}}cur = cur.next;}}//得到单链表的长度public int size(){return this.size;}//输出链表的内容public void display(){ListNode cur=first;while ( cur != null ){System.out.println(cur.val);cur=cur.next;}}public void clear(){first=null;last=null;}
}

链表的相关题目

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

class Solution {public ListNode removeElements(ListNode head, int val) {if ( head==null ){return null;}ListNode pre=head;ListNode cur=head.next;while ( cur!=null ){if ( cur.val==val ){cur=cur.next;pre.next=cur;}else{pre=cur;cur=cur.next;}}if ( head.val==val ){head=head.next;}return head;}
}

反转一个单链表

https://leetcode.cn/problems/reverse-linked-list/description/

将每一个结点的指向翻转一下,不需要重新遍历什么的。

class Solution {public ListNode reverseList(ListNode head) {if ( head==null ){return null;}ListNode cur = head.next;ListNode pre = head;pre.next = null;while ( cur != null ){ListNode nextNode = cur.next;cur.next = pre;pre = cur;cur = nextNode;}return pre;}
}

链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

用快慢指针可以在O(n)的时间复杂度完成。

class Solution {public ListNode middleNode(ListNode head) {if ( head == null ){return null;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}
}

链表中倒数第k个结点

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

用快慢指针的方法,快指针先跑k个,然后慢指针和快指针再按相同的速度跑 

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if ( head == null ){return null;}ListNode fast = head;ListNode slow = head;while (k != 0){if (fast != null){fast = fast.next;k--;}else{return null;}}while ( fast != null ){slow = slow.next;fast = fast.next;}return slow;}
}

 

相关文章:

【剧前爆米花--爪哇岛寻宝】Java实现无头单向非循环链表和无头双向链表与相关题目

作者&#xff1a;困了电视剧 专栏&#xff1a;《数据结构--Java》 文章分布&#xff1a;这是关于数据结构链表的文章&#xff0c;包含了自己的无头单向非循环链表和无头双向链表实现简单实现&#xff0c;和相关题目&#xff0c;想对你有所帮助。 目录 无头单向非循环链表实现 …...

学习MvvmLight工具

最近学习了一下MvvmLight&#xff0c;觉得有些功能还是挺有特色的&#xff0c;所以记录一下 首先新建也给WPF程序 然后在Nuget里面安装MvvmLightLib 包&#xff0c;安装上面那个也可以&#xff0c;但是安装上面那个会自动在代码里面添加一些MvvmLight的demo &#xff0c;安装M…...

基于BiLSTM+CRF医学病例命名实体识别项目

研究背景 为通过项目实战增加对命名实体识别的认识&#xff0c;本文找到中科院软件所刘焕勇老师在github上的开源项目&#xff0c;中文电子病例命名实体识别项目MedicalNamedEntityRecognition。对其进行详细解读。 原项目地址&#xff1a;https://github.com/liuhuanyong/Med…...

05 C语言数据类型

05 C语言数据类型 1、数据类型 编程语言对数据类型分为两派&#xff1a;一种认为要注重&#xff0c;一种认为可以忽视。 C语言类型 1、整数 : char < short < int < long < long long &#xff0c;bool 2、浮点数&#xff1a;float < double < long doub…...

C++11:右值引用和移动语义

文章目录1. 左值和右值表达式1.1 概念1.2 左值和右值2. 左值引用和右值引用2.1 相互引用2.2 示例代码2.3 左值引用使用场景缺点2.4 右值引用和移动语义小结2.5 移动赋值2.6 右值引用的其他使用场景右值引用版本的插入函数3. 完美转发3.1 万能引用3.2 如何实现完美转发3.3 完美转…...

tcpdump网络抓包工具

tcpdump 是一个强大的网络抓包工具&#xff0c;在分析服务之间调用时非常有用。可以将网络中传送的数据包抓取下来进行分析。tcpdump 提供灵活的抓取策略&#xff0c;支持针对网络层、协议、主机、网络或端口的过滤&#xff0c;并提供 and、or、not 等逻辑语句来去掉不想要的信…...

MaxCompute SQL中的所有保留字与关键字如下

– MaxCompute SQL中的所有保留字与关键字如下 注意 命名表、列或分区时&#xff0c;不要使用保留字与关键字&#xff0c;否则可能会报错。 保留字不区分大小写。 在对表、列或是分区命名时如若使用关键字&#xff0c;需给关键字加符号进行转义&#xff0c;否则会报错。 % &am…...

Kafka 压缩算法

压缩 (compression) : 用时间换空间的思想 用较小的 CPU 开销获得磁盘少占用或网络 I/O 少传输 Kafka 消息分两层&#xff1a; 消息日志组成 : n 个消息集合消息集合 (message set) 组成 : n 条日志项 (record item)日志项封装了消息 (message)Kafka 在消息集合层上进行写入…...

关于React Hook(18)

useState&#xff08;&#xff09;&#xff1a;&#x1f449;详情 &#xff08;必须“有条件地调用”&#xff1b;注意避免冗余状态的产生&#xff09; 关于useState的两种使用方式的区别&#xff1a;&#x1f449;详情 关于batch机制&#xff1a;有条件地调用一些状态的set方…...

计算机网络:BGP协议

BGP协议 与其他AS的邻站BPG发言人交换信息。 交换的网络可达性信息&#xff0c;即要到达某一个网络所要经历的一系列AS 发生变化时&#xff0c;更新有变化的部分 BGP协议交换信息的过程&#xff1a;所交换的网络可达性信息就是要到达某一个网络所要经历的一系列AS&#xff…...

91. 解码方法 ——【Leetcode每日刷题】

91. 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 &#xff1a; ‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” 要 解码 已编码的消息&#xff0c;所有数字必须基于上述映射的方法&#xff0c;反向映射回字母&#xff08;可能有多种方法&#xff0…...

人体存在传感器成品方案,精准感知静止存在,实时智能化感控技术

随着现今智能时代的发展&#xff0c;酒店也越来越趋于智能化&#xff0c;也在不断地推行智慧酒店&#xff0c;这也给人们入住酒店提供了良好的体验。 人体存在感知是智能酒店中极其重要的一项应用技术&#xff0c;只有智能设备通过精准地感知人体存在&#xff0c;才能更好地做…...

mysql连接池的实现

目录 1 池化技术 2 什么是数据库连接池 3 为什么使用数据库连接池 3.1 不使用连接池 3.2 使用连接池 3.3 长连接和连接池的区别 4 数据库连接池运行机制 5 连接池和线程池的关系 6 线程池设计要点 6.1 连接池设计逻辑 构造函数 初始化 请求获取连接 归还连接 析…...

哪种类型蓝牙耳机佩戴最舒服?舒适度最好的蓝牙耳机推荐

如果您想在外出时听自己喜欢的音乐&#xff0c;您需要佩戴耳机&#xff0c;当前的耳机都足够小&#xff0c;可以将它们放在口袋里&#xff0c;即使它们在充电盒中也是如此&#xff0c;舒适度一直都是人们所追求的&#xff0c;舒适之余&#xff0c;佩戴同样稳固更加令人安心&…...

2020蓝桥杯真题洁净数 C语言/C++

题目描述 小明非常不喜欢数字 2&#xff0c;包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2&#xff0c;小明将它称为洁净数。 请问在整数 1 至 n 中&#xff0c;洁净数有多少个&#xff1f; 输入描述 输入的第一行包含一个整数 n(1≤n≤10^6)。 输出描述 输…...

【随笔二】useReducer详解及其应用场景

前言 useReducer 实际上是 useState 的升级版&#xff0c;都是用来存储和更新 state&#xff0c;只是应用的场景不一样。 一般情况下&#xff0c;我们使用 useState 就足够项目需要了&#xff0c;不多当遇到以下场景时&#xff0c;使用useReducer 会更好些 。 状态逻辑复杂&…...

打怪升级之istringstream介绍

istringstream类 istringstream本质不是类&#xff0c;是一个宏&#xff0c;或者说是一个流&#xff1a; typedef basic_istringstream<char> istringstream;istringstream从basic_istringstream的char专用项而来。这一部分让人看得摸不着头脑的原因是因为大量使用了st…...

系统重装漏洞

zzcms系统重装漏洞 一、配置zzcms环境 1. 使用小皮搭建zzcms框架 2. 安装zzcms 按照下面的操作进行,傻瓜式操作即可 3. 打开网站 二、漏洞利用 在访问install目录的默认文件后,会出现zzcms安装向导 http://www.zzcms.com/install/index.php 但是会显示 “安装向导…...

C++面向对象编程之五:友元(friend)

C中&#xff0c;允许一个类的非共有成员被这个类授予友元&#xff08;friend&#xff09;关系的全局函数&#xff0c;另一个类&#xff0c;或另一个类中的成员函数访问。友元不是一个类中的成员&#xff0c;所以它们不受声明出现部分的访问权限&#xff08;public&#xff0c;p…...

[手写OS]动手实现一个OS 之X86实模式下的汇编开发

[手写OS]动手实现一个OS 之X86实模式下的汇编开发 x86实模式下 汇编开发是一个 intel x86实模式中的汇编程序开发类型。它涉及操纵几个16位处理器寄存器&#xff0c;并仅处理内存中的物理地址&#xff08;与受保护模式相对&#xff09;。 这种类型的编程中最广为人知的应用就…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...