【Java数据结构】 链表
一. ArrayList的缺陷
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// ...
// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...
// 数组:用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
// ...
}
二. 链表
1 链表的概念及结构




- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
- 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2 链表的实现
1、无头单向非循环链表实现
链表的基本表示:
static class ListNode{public int val;public ListNode next;public ListNode(int data){this.val=data;}}public ListNode head;//链表的头
对应的方法:
public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear() ;public void display();
}
实现对应的方法:
(1)display
public void display() {ListNode cur=head;//不能改变头的引用while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}
(2)size
public int size() {int len=0;ListNode cur=head;while (cur!=null){len++;cur=cur.next;}return len;}
(3)contains
public boolean contains(int key) {ListNode cur=new ListNode(key);while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}
(4)addFirst/头插
public void addFirst(int data) {ListNode listNode=new ListNode(data);//该节点是新的头节点listNode.next=head;head=listNode;}
(5)addFirst/尾插
public void addLast(int data) {ListNode listNode=new ListNode(data);if(head==null){head=listNode;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=listNode;}
(6)addIndex/任意位置插
public void addIndex(int index, int data) {int len=size();if (index<0||index>len){new IndexOutOfBoundary("index输入有误");return;}if(index==0){addFirst(data);return;}if(index==len){addLast(data);return;}int curLen=0;ListNode cur=head;ListNode listNode=new ListNode(data);while(curLen<index-1){curLen++;cur=cur.next;}listNode.next=cur.next;cur.next=listNode;}
(7)remove
public void remove(int key) {if(head==null){//链表为空return;}if(head.val==key){//删除的位置在头节点head=head.next;return;}ListNode pre=findPreNodeOfKey(key);if(pre!=null){ListNode del=pre.next;//找到需要删除的节点pre.next=del.next;}}private ListNode findPreNodeOfKey(int key){ListNode cur=head;while(cur.next!=null){//最后一个节点也已经判断过了if (cur.next.val==key){return cur;}cur=cur.next;}return null;}
(8)removeAllKey
public void removeAllKey(int key) {if(head==null){return;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur= cur.next;}else {prev=prev.next;cur= cur.next;}}//把前面的除头节点之外的都删完之后删除头节点if (head.val==key){head=head.next;}}
(9)clear
public void clear() {ListNode cur=head;while (cur!=null){ListNode curN=cur.next;cur.next=null;//基本数据类型的val不需要回收cur=curN;}}
三.链表相关题目
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution{public ListNode removeElements(ListNode head,int data){if(head==null){return head;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(cur.val==data){prev.next=cur.next;cur=cur.next;}else{prev=prev.next;cur=cur.next;}}if(head.val==data){head=head.next;}return head;}}
2. 反转一个单链表。
可以采取不停的进行头插,将后面的节点不停的插到前面
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ ListNode curN=cur.next;cur.next=head;head=cur;cur=curN;}return head;}
}
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {if(head==null){return head;}ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}
import java.util.*;/** public class ListNode {* int val;* ListNode next = null;* public ListNode(int val) {* this.val = val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/public ListNode FindKthToTail (ListNode pHead, int k) {int count=0;ListNode f=pHead;while(f!=null){count++;f=f.next;}if(k>count||k<=0){return null;}if(pHead==null){return pHead;}// write code hereListNode prev=pHead;ListNode cur=pHead;while((k-1)!=0){cur=cur.next;k--;}while(cur!=null&&cur.next!=null){prev=prev.next;cur=cur.next;}return prev;}
}
经过重新调整,除了计算出有多少元素,防止多删除之外,可以在快指针走的时候就进行判断,走太多就会超过限制,那么就会走到空指针出,也可以判断
while((k-1)!=0){cur=cur.next;k--;if(cur==null){return null;}}
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode cur1=list1;ListNode cur2=list2;ListNode newHead=new ListNode();ListNode tmp=newHead;if(cur1==null&&cur2==null){return null;}while(cur1!=null&&cur2!=null){if(cur1.val<=cur2.val){tmp.next=cur1;cur1=cur1.next;tmp=tmp.next;}else{tmp.next=cur2;cur2=cur2.next;tmp=tmp.next;}}if(cur1!=null){tmp.next=cur1;cur1=cur1.next;tmp=tmp.next;}if(cur2!=null){tmp.next=cur2;cur2=cur2.next;tmp=tmp.next;}return newHead.next;}
}
- 利用两个链表,一个存放小于x的值,一个存放大于x的值
- 要注意的是最后的判断条件,可能不存在小于x的,则直接返回第二个链表;且如果第二个链表不为空,链表结尾要置空,防止越界。
import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode() { }ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereListNode list1start=null;ListNode list1end=null;ListNode list2start=null;ListNode list2end=null;while(pHead!=null){if(pHead.val<x){if(list1start==null){list1start=list1end=pHead;}else{list1end.next=pHead;list1end=list1end.next;}}else{if(list2start==null){list2start=list2end=pHead;}else{list2end.next=pHead;list2end=list2end.next; } }pHead=pHead.next;}if(list1start==null){return list2start;}list1end.next=list2start;if(list2start!=null){list2end.next=null;}return list1start;}
}
7. 链表的回文结构。
import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head == null) return true;ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//slow 指向的位置 就是中间节点//2.进行翻转ListNode cur = slow.next;while (cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//3.判断回文while (head != slow) {if(head.val != slow.val) {return false;}if(head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;}
}
分别去求两个链表的长度,让长的链表去走两个链表的差值
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pl=headA;ListNode ps=headB;int len1=0;int len2=0;while(pl!=null){pl=pl.next;len1++;}while(ps!=null){ps=ps.next;len2++;}pl=headA;ps=headB;int k=len1-len2;if(k<0){pl=headB;ps=headA;k=0-k;} while(k!=0){pl=pl.next;k--;}while(pl!=ps){pl=pl.next;ps=ps.next;}//若两个链表不相交if(pl==null){return null;}return pl;}
}
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow){return true;}}return false;}
}
- 为什么快指针每次走两步,慢指针走一步可以?
- 快指针一次走3步,走4步,...n步行吗?

起点到入口点的距离和相遇点到入口点的距离相等
此时slow从开头处开始走,fast从相遇点开始走,以相同的速度运动,相遇时则为相交点
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){break;}}if(fast==null||fast.next==null){return null;}slow=head;while(slow!=fast){fast=fast.next;slow=slow.next;}return slow; }
}

相关文章:

【Java数据结构】 链表
【本节目标】 1. ArrayList 的缺陷 2. 链表 3. 链表相关 oj题目 一. ArrayList的缺陷 上节课已经熟悉了ArrayList 的使用,并且进行了简单模拟实现。通过源码知道, ArrayList 底层使用数组来存储元素: public class ArrayList<E>…...

前端——Ajax和jQuery
一、Ajax Ajax即“Asynchronous Javascript And XML”(异步 JavaScript 和 XML), 通过 JS 异步的向服务器发送请 求并接收响应数据。 同步访问:当客户端向服务器发送请求时,服务器在处理的过程中,浏览器…...

C++-vector模拟实现
###vector底层相当于是数组,查看源码可以发现,这个类的私有成员变量是三个迭代器;在实现时迭代器就可以当作是vector里面的元素的指针类型; ###vector是一个类模板,实现时也应当按照这样的写法用一个模板去实现&#…...

Activity
69[toc] 1.启停活动页面 1.Activity启动和结束 从当前页面跳到新页面 startActivity(new Intent(this, ActFinishActivity.class));从当前页面返回上一个页面,相当于关闭当前页面 finish();2.Activity生命周期 官方描述生命周期 onCreate:创建活…...
【力扣 | SQL题 | 每日四题】力扣1581, 1811, 1821, 1831
今天的题目就1811这个比较难,其他非常的基础。 1. 力扣1581:进店却未进行过交易的顾客 1.1 题目: 表:Visits ---------------------- | Column Name | Type | ---------------------- | visit_id | int | | customer…...
洛谷【P1955 [NOI2015] 程序自动分析】
反思: 这道题一眼就是并查集 但是数据太大 mle和re都是有可能的我看了题解才知道是离散化数组加并查集离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行 离散化思路: 需要一个离散记录数组----ls[N]用来记录下出现的数 步骤: …...

Swift并发笔记
1.同步和异步 说到线程的执行方式,最基本的一组概念是同步和异步。所谓同步,就是在操作执行完成之前,运行操作的这个线程都会被占用,直到函数最终被抛出或返回。Swift5.5之前,func关键字声明的所有的函数都是同步的。…...
React 组件命名规范
在 React 项目中,如果希望保持组件命名的一致性,并防止在引入时出现不同名称的问题,可以遵循以下的组件规范: 1、默认导出组件: 所有特殊要求的组件(如页面组件或根组件)应该使用 export defau…...
eNSP网络配置指南:IP设置、DNS、Telnet、DHCP与路由表管理
1.eNSP基本操作和路由器IP配置命令 登录设备:通过Console口或通过eNSP的Telnet/SSH客户端登录到设备。进入特权模式:输入system-view进入系统视图。接口配置: 进入接口视图,例如interface GigabitEthernet0/0/0。配置IP地址和子网…...

初步认识产品经理
产品经理 思考问题的维度 1️⃣为什么要抓住核心用户? 所有和产品有关系的群体就是用户,存在共性和差异了解用户的付费点,更好的优化产品是否使用:(目标用户-已使用产品:种子用户-尝鲜;核心用…...

web前端面试中拍摄的真实js面试题(真图)
web前端面试中拍摄的真实js面试题(真图) WechatIMG258.jpeg WechatIMG406.jpeg WechatIMG407.jpeg WechatIMG922.jpeg WechatIMG1063.jpeg © 著作权归作者所有,转载或内容合作请联系作者 喜欢的朋友记得点赞、收藏、关注哦!!…...
python 人工智能 机器学习 当损失函数的数值变成 `nan` 时,这通常意味着在模型训练过程中出现了数值不稳定性以及解决办法,数据分析
当损失函数的数值变成 nan 时,这通常意味着在模型训练过程中出现了数值不稳定性。以下是一些可能导致这个问题的原因以及相应的解决方法: 1. **学习率过高**:如果学习率设置得过高,可能会导致梯度爆炸,从而导致损失函…...

Kafka快速实战与基本原理详解
笔记:https://note.youdao.com/ynoteshare/index.html?id=b0357bdb4821ed2e35ecdbdacd65aa06&type=note&_time=1727570043631 启动kafka之前先启动zookper 看看ZK里面都有什么数据 : 刚开始什么数据都没有 接下来启动kafka,启动好后,日志在这里看: 启动好了kaf…...

tftp传文件被服务器拒绝进入tftp: server error: (768) Access to staonline.pcap denied
环境:测试一个ac下挂ap,ap下的抓包文件传出时,出现问题: ac的wan口ip是192.168.186.167/24,gw是192.168.186.1,下挂ap的ip是192.168.202.199/24,ac上开子接口192.168.202.1/24,ac上开…...
express,生成用户登录后的 token
在 Node.js 中使用 Express 框架生成用户登录后的 token,通常会涉及到以下几个步骤: 设置 Express 应用:首先,你需要有一个基本的 Express 应用。安装必要的中间件:例如 jsonwebtoken(JWT)用于…...

银河麒麟桌面操作系统修改默认Shell为Bash
银河麒麟桌面操作系统修改默认Shell为Bash 💐The Begin💐点点关注,收藏不迷路💐 在银河麒麟桌面操作系统(ARM版)中,若要将默认Shell从Dash改为Bash,可执行以下步骤: 打开…...
卷积神经网络(Convolutional Neural Networks, CNN)
卷积神经网络(Convolutional Neural Networks, CNN)是深度学习领域中用于处理具有网格结构的输入(如图像和视频)的神经网络模型。下面以最简单、直观的方式概述CNN的主要流程及其基本概念: 1. 输入层 概念:…...

SpringBoot系列 启动流程
文章目录 SpringApplicationSpringApplication#run 启动流程BootstrapContextSpringApplicationRunListenersprepareEnvironmentconfigureEnvironmentconfigurePropertySourcesconfigureProfiles 上下文初始化prepareContextrefreshContextprepareRefreshobtainFreshBeanFactor…...

vgg19提取特征
一般来说,大家使用VGG16,用的是第四列的网络架构,而使用VGG19,使用的就是第六列的网络架构。 使用vgg进行提取特征,在这个项目中,使用的就是每一块卷积层的第一层。 import torch.nn as nn from torchvis…...
Qt 中的 QChartView
深入理解 Qt 的 QChartView:图表展示与交互 QChartView 是 Qt Charts 模块中的一个核心类,它用于在 Qt 应用程序中显示图表,并支持多种用户交互方式。它继承自 QGraphicsView,通过封装 QChart,为用户提供了强大的图表…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...

AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...

相关类相关的可视化图像总结
目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系,可直观判断线性相关、非线性相关或无相关关系,点的分布密…...

如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...