Java链表LinkedList经典题目
一.LinkedList的方法
首先先看一下链表的方法:
| 方法 | 解释 |
| boolean add(E e) | 尾插 |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List subList(int fromIndex, int toIndex) | 截取部分 list |
二.反转链表
题目对应LeetCode:206. 反转链表
/*** 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 || head.next==null){return head;}ListNode pr=head;ListNode cur=head.next;ListNode p=cur.next;while(cur!=null){cur.next=pr;pr=cur;cur=p;if(p!=null){p=p.next;}}head.next=null;return pr;}
}
思路:从前往后将每一个节点的next改成其前一个节点。
定义三个ListNode变量指向三个节点,cur指向的是当前要改变next的节点,pr指向的是cur.next要指向的节点,p是记录的作用,如果cur的next变成指向前面了,那么本来cur后面一个节点就丢失了,无法完成反转。
三.快慢指针在链表的应用
不少题目的解题关键就在快慢指针。
首先是最经典的应用:LeetCode:876. 链表的中间结点
题目意思就是返回中间结点,最笨的办法就是将链表遍历一遍,看看有多少个结点,然后再遍历出中间结点。这里使用快慢指针可以一步到位。
/*** 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;}
}
定义一个快指针和一个慢指针,让快的一下走两步,慢的一下走一步,这样走到最后停止时,slow刚好在中间结点上。
这个可以说是一个元问题,很多链表的题目都有这道题快慢指针的影子。
像非常经典的回文链表问题:CR 027. 回文链表,用的都是快慢指针的思想。
四.相交链表
题目对应LeetCode:160. 相交链表
这是题目的描述:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

由例图可以看出,在两个单链表相遇之后,交点后面的结点都是相同的。先考虑最简单的情况,如果两个链表的长度相同,那么直接从头开始一个一个遍历,知道找到交点。但是这个方法在双方长度不一时用不了。既然用不了,那我们就借着这个思路改一下,给短的链表补上不就行了,换句话说,链表从后往前对齐,长链表前面多的那部分不可以有结点,直接跳过即可,这样问题就解决了。
/*** 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) {if(headA==null && headB==null){return null;}int len=0;int lb=0;int la=0;ListNode cur=headA;while(cur!=null){la++;cur=cur.next;}cur=headB;while(cur!=null){lb++;cur=cur.next;}ListNode l=headA;ListNode s=headB;len=la-lb;if(la<lb){l=headB;s=headA;len=lb-la;}while(len!=0){l=l.next;len--;}while(l!=s && l!=null && s!=null){l=l.next;s=s.next;}if(l==s && l!=null){return l;}else{return null;}}
}
五.链表的环问题
1.是否存在环
题目对应LeetCode:141. 环形链表
应用的也是快慢指针的思想,这个就像在操场上跑步一样,如果一快一慢,而且还是闭环的话,那么两个人一定会相遇。这个同理,如果成环,那么两个指针也是会相遇的。
/*** 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) {if (head == null) return false;ListNode slow=head;ListNode fast=head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){return true;}}return false;}
}
2.返回入环后的第一个结点
题目对应LeetCode:142. 环形链表 II
这个题里面有一个数学推导,直接说结果,起点到入环后第一个结点的距离=快慢指针相遇的交点到入环后第一个结点的距离。
这个推导并不难,就初中生水平,大家可以自己试一下。
/*** 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(true){if(fast==null || fast.next==null){return null;}slow=slow.next;fast=fast.next.next;if(fast==slow){break;}}slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}return slow;}
}
相关文章:
Java链表LinkedList经典题目
一.LinkedList的方法 首先先看一下链表的方法: 方法解释boolean add(E e)尾插void add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一…...
【cocos creator】2.x,伪3d拖拽,45度视角,60度视角,房屋装扮
伪3d拖拽,45度视角,60度视角 工程下载:(待审核) https://download.csdn.net/download/K86338236/89530812 dragItem2.t s import mapCreat2 from "./mapCreat2";const {ccclass, property } = cc._decorator; /*** 拖拽类,挂在要拖拽的节点上*/ @ccclass export…...
【thingsbord源码编译】 显示node内存不足
编译thingsbord显示报错 FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory问题原因分析 重新安装java版本 编译通过...
内存巨头SK海力士正深化与TSMC/NVIDIA合作关系,开发下一代HBM
据BusinessKorea报道,内存巨头SK海力士正深化与台积电(TSMC)及英伟达(NVIDIA)的合作关系,并计划在9月的台湾半导体展(Semicon Taiwan)上宣布更紧密的伙伴关系。 SK海力士与台积电的合作历史已久。2022年,台积电在其北美技术研讨会上宣布成立O…...
基于Pinia的WebSocket管理与优化实践(实现心跳重连机制,异步发送)
WebSocket作为一种全双工通信协议,允许服务器和客户端之间建立持久的连接,提供了比传统HTTP请求更为高效的数据交换方式。本文将探讨如何使用Pinia状态管理库在Vue应用中优雅地管理和优化WebSocket连接,以实现稳定、高效的实时数据传输。 环境…...
Perl词法作用域:自定义编程环境的构建术
🎭 Perl词法作用域:自定义编程环境的构建术 在Perl编程中,词法作用域(lexical scoping)是一种控制变量可见性的方式,它允许变量在特定的作用域内可见,从而避免变量名的冲突。Perl提供了灵活的机…...
vscode使用ssh连接远程服务器
开工啦 vscode连接远程服务器(傻瓜式教学) 正常根据上面文章的步骤就可以连接了 报错可以尝试的文章: VScode通过remote ssh连接虚拟机 & 报错过程试图写入的管道不存在(已解决) vscode remote ssh linux[血泪…...
linux 常用和不那么常用命令记录02 磁盘占用
常用的磁盘相关命令 du 有的时候我们想要查询一个文件所占用的磁盘空间大小,可以使用du命令来查看 命令 配置 参数 du [options] [files or directories]-h:以人类可读的格式显示输出(例如 KB、MB、GB)。 -s…...
mybatis日志记录方案
首先对指定表进行监控 对表进行监控,那么就要使用的是statementInterceptor 拦截器 使用拦截器那么就要写intercepts写拦截条件进行拦截 监控只对与增删改 查询不进行监控 对于字段的监控,是谁修改了字段,那么就进行报警,或者提醒 消息提醒使用钉钉机器人进行消息提醒 P…...
【LeetCode】最长连续序列
目录 一、题目二、解法完整代码 一、题目 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入:nu…...
Windows下终端Kafka指令常用操作
1、创建Topic kafka-topics.bat --create --bootstrap-server localhost:9092 --replication-factor 1 --partitions 1 --topic test 2、查看Topic列表 kafka-topics.bat --list --bootstrap-server localhost:9092 3、设置Topic最大消息大小 kafka-topics.bat --bootstrap-s…...
QT---lineEdit相关信号
1.returnPressed信号 connect(ui.lineEdit_passWord, &QLineEdit::returnPressed, []() { // 输入密码回车后,调用校验密码接口ui.lineEdit_passWord->clearFocus(); //失去焦点on_param_confirmBtn_clicked();});2.输入后失去焦点才获取编辑框内新信息 参…...
基于vue的地图特效(飞线和标注)
这段代码的主要功能是在页面加载完成后,初始化一个 echarts 地图图表,并配置了相关的地理数据、散点数据、线条数据以及样式效果,最后在指定的 div 元素中进行展示。 需要再vue中的框架实现,不能单独直接运行。 标注 type: effe…...
生物环保技术有哪些缺点或者局限性呢
生物环保技术,作为一种利用生物学原理和技术来处理环境污染的方法,虽然具有绿色环保、高效节能等优点,但也存在一些缺点和局限性。以下是对这些缺点和局限性的详细分析: 一、受环境因素影响大 生物环保技术的效果往往受到环境因…...
我被手机所伤,竟如此憔悴。
临睡前,刚刷完小视频,感觉好无聊。一阵阵空虚感袭来。看看时间,哦,原来我下班后一直从6点刷视频到11点。 哎,太空虚了,又马上要睡觉了,为什么会这么难受呢?明明我大学,高中&#x…...
【深度学习】第3章实验——回归模型
根据相关数据集进行回归分析 1. import statsmodels.api as sm # df.loc[:, ...] 表示选择所有行。 # df.columns ! mpg 创建一个布尔数组,指示哪些列不等于 mpg。 # df.loc[:, df.columns ! mpg] 选择 df 中所有行和列名不等于 mpg 的所有列。 x df.loc[:,df.col…...
MYSQL 四、mysql进阶 8(索引优化与查询优化)
都有哪些维度可以进行数据库调优?简言之: 索引失效、没有充分利用到索引——建立索引关联查询太多JOIN(设计缺陷或不得已的需求)——SQL优化服务器调优及各个参数设置(缓冲、线程数等)——调整my.cnf数据过…...
python | pyvips,一个神奇的 Python 库
本文来源公众号“python”,仅用于学术分享,侵权删,干货满满。 原文链接:pyvips,一个神奇的 Python 库! 大家好,今天为大家分享一个神奇的 Python 库 - pyvips。 Github地址:https…...
STM32利用FreeRTOS实现4个led灯同时以不同的频率闪烁
在没有接触到FreeRTOS时,也没有想过同时叫两个或两个以上的led灯闪烁的想法,接触后,发现如果想叫两个灯同时以不同的频率闪烁,不能说是不可能,就算是做到了也要非常的麻烦。但是学习了FreeRTOS后,发现要想同…...
深入Laravel事件系统:创建与使用事件的指南
Laravel的事件系统是一种强大的机制,它允许你将应用程序的行为封装成事件,然后在适当的时候触发这些事件。这不仅有助于代码的解耦,还提高了应用程序的可维护性和可扩展性。本文将详细介绍如何在Laravel中创建和使用事件,包括事件…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
