Java单链表题目
Java链表题目练习
- 移除链表元素
- 反转单链表
- 链表的中间节点
- 返回倒数第K个节点
- 合并两个有序列表
- 判断链表是否回文
学习了知识,就要进行其检验自己是否真正学会,练习题目来加强对知识的理解,今天就来练习一下链表题目
移除链表元素
目的:就是给定一个数val,删除链表中所有节点值等于val的节点
思路:
就是利用快慢指针进行查找,快的指针找到的话,就让其慢的指针.next = 快指针.next;快指针指向下一个,如果没有找到的话,两个指针同时向后移动,一直保持一个距离
1.就是定义快慢指针pre和cur,刚开始pre = head ,cur = head.next;
2.pre存放要找值的前一个个节点,cur指向的就是要找的节点,就直接将
找到要删除的节点
pre.next = cur.next;
cur = cur.next;
没找到(都继续往后找)
pre = cur;
cur = cur.next;
3.这里上面我们并没有检查头节点,是从头节点后面节点开始检查的,因此最后要检查一下头节点
如果要删除 head = head.next;
先找要删除节点
找到就将其前一个节点的指向改变
删除后,就继续往后找
/*** 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 val) {//判断head是否为nullif(head==null){return null;}ListNode pre = head;ListNode cur = head.next;//从第二个节点开始找while(cur!=null){if(cur.val==val){pre.next = cur.next;//改变指向cur = cur.next;//往后走}else{//没找到就都往后移动pre = cur;cur = cur.next;}}//检查头是否也要删除if(head.val==val){head = head.next;}//最后返回新的头节点return head;}
}
这里其实可以将检查头节点放在最前面
但是为什么我们不这样做呢,因为这样的话,改变了头节点,头节点就变了,有可能下一个节点也是要删除的,这样可能多次改变头节点,可能会比较繁琐,因此把这一步骤放在最后,无论如果只需要判断一次
反转单链表
目的:将一个链表反转过来
思路:定义一个cur用来指向head.next,头的后面一个,让后面的一个一个链接到前面,直到最后的null,头一直在改变
1.一个cur用来遍历整个链表
2.一个Ncur保存cur的后面链表的首地址,因为每次都会改变cur.next,如果不报保存一下,后面的链表就找不到了
cur = head . next;
while(cur!=null)
{
Ncur = cur.next;//保存后面链表地址
cur.next = head;//修改其指向head
head = cur;//头变成cur
}
/*** 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) {//先判断是否为null或者就一个节点的话直接返回if(head==null){return null;}if(head.next==null){return head;}//先保存一份,删除后就找不到了ListNode cur = head.next;//头变成尾,下面置为nullhead.next=null;while(cur!=null){ListNode Ncur = cur.next;cur.next = head;head = cur;cur = Ncur;}return head;}
}
链表的中间节点
目的:获取中间节点,如果有两个中间节点,就返回其中第二个节点
思路:使用快慢指针,定义一个fast和slow指针,fast一次走两步,slow一次走已步,同时从head开始,当fast走到链表结束的时候,这时候的slow正好符合我们要找的中间节点的要求
原理:时间一样fast的速度是slow的2倍,fast走完,slow正好走一半
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
class Solution {public ListNode middleNode(ListNode head) {//注意判断一下,头是否为空if(head==null){return null;}//快慢指针ListNode fast = head;ListNode slow = head;//奇数个节或者点偶数个节点//只要有一个不符合一个就说明找到了while(fast!=null&&fast.next!=null){fast = fast.next.next;slow = slow.next;}//最后返回slow所指向的节点return slow;}
}
返回倒数第K个节点
目的:找到倒数第K个节点,返回其该节点的值,并且题目已将保证了K是有效的
思路:快慢指针fast和slow从头开始,1.先让fast先走k-1步后,2.在让其一起走,最总fast走到末尾就查找结束
原理:找倒数第K个节点,其倒数第K个节点到倒数第一个节点只需要k-1步就可以,相差两个距离
那我们先让fast走k-1步,这样fast就与slow的距离固定为k-1,也就是倒数第K个节距离倒数第一个节点,这时候在让其一起走,直到fast走到最后一个,slow正好是我们要找的节点
同样的速度,同样的时间,固定的距离向后走
class Solution {public int kthToLast(ListNode head, int k) {//1.先确定倒数第一个与要查找节点之间间隔//2.将这个间隔为fast和slow之间的间隔//3.如果fast走到最后,slow就是要找的if(head==null){return -1;}ListNode fast = head;ListNode slow = head;int count = 0;//先让fast走k-1步,固定二者之间距离while(count!=k-1){fast = fast.next;count++;}//让后一起向后走//当fast走到倒数第1个,slow正好是倒数第K个,二者间距为k-1while(fast.next!=null){fast = fast.next;slow = slow.next;}//返回节点的值return slow.val;}
}
合并两个有序列表
目的:将两个非递减顺序的单链表合并为一个新的非递减单链表
思路:1.先定义一个头节点 ,2.遍历两个列表,进行判断,拼接两个列表中val值小的节点,拼接完往后走 3.直到循环到有一个链表结尾了,将另一个列表剩下拼接后面就行了
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//1.先创建一个节点用来当头//2.比较两个列表数值,进行链接//3.如果出现null就说明有一个结束了,就将另一个链接就行了ListNode Nhead = new ListNode(-1);ListNode tem = Nhead;//用来存放ListNode cur1 = list1;ListNode cur2 = list2;//遍历直到有一个链表到了结束while(cur1!=null&&cur2!=null){if(cur1.val<cur2.val){tem.next = cur1;tem = cur1;cur1 = cur1.next;}else{tem.next = cur2;tem = cur2;cur2 = cur2.next;}}//将另一个为遍历完的进行拼接到后面if(cur1!=null){tem.next = cur1;}if(cur2!=null){tem.next = cur2;}return Nhead.next;}
}
判断链表是否回文
题目:判断一个链表是否是回文的
思路:我们首先想的就是让其链表前后一起遍历进行比较,但是我们怎么让其后面的向前走呢
1.找到中间节点(fast和slow快慢指针,前面已经讲过了)
2.将中间以后的链表逆置(定义一个cur = slow.next; 从cur开始将节点指向逆向翻转,每次翻转完成slow向后走一步slow=cur,让slow走到尾部)
3.前后分别遍历比较(一个向前一个向后开始进行比较val值是否相同)
public class PalindromeList {public boolean chkPalindrome(ListNode head) {//1.找到中间节点//2.将中间节点后面节点逆置//3.比较if(head==null){return true;}ListNode headA = head;//找中间节点ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null){fast = fast.next.next;slow = slow.next;}//后面逆置ListNode cur = slow.next;while(cur!=null){ListNode Ncur = cur.next;cur.next =slow;slow = cur;cur = Ncur;}//比较while(headA!=slow){if(headA.val!=slow.val){return false;}if(headA.next==slow){return true;}headA = headA.next;slow = slow.next;}return true;}
}
相关文章:
Java单链表题目
Java链表题目练习 移除链表元素反转单链表链表的中间节点返回倒数第K个节点合并两个有序列表判断链表是否回文 学习了知识,就要进行其检验自己是否真正学会,练习题目来加强对知识的理解,今天就来练习一下链表题目 移除链表元素 目的ÿ…...
springboot入门-controller层
在 Spring Boot 中,Controller 层是处理 HTTP 请求的核心组件,负责接收客户端请求、调用业务逻辑(Service 层)并返回响应。其核心原理基于 Spring MVC 框架,通过注解驱动的方式实现请求的路由和参数绑定。以下是 Contr…...
游戏引擎学习第245天:wglChoosePixelFormatARB
Blackboard: PBO(像素缓冲对象) 我们将一起编写一个完整的游戏。老实说,我原本以为我们会花更长时间来实现异步纹理上传,结果我们只用了两天时间,主要原因是我们没有设置标志来真正告诉程序下载纹理,所以这…...
中国大陆DNS服务选择指南:阿里云VS AWS,合规性与最佳实践
导语 在中国大陆开展互联网业务时,DNS服务的选择不仅关乎性能,更涉及合规性问题。本文将深入探讨DNS服务商选择的自由度、阿里云与AWS DNS服务的优劣势,以及如何在确保合规的同时优化您的域名解析策略。无论您是初创公司还是跨国企业,这份指南都将助您在复杂的中国互联网环境中…...
LLaMa Factory大模型微调
LLaMa Factory大模型微调 大模型微调平台&硬件LLaMA-Factory安装hfd下载hugging face模型自我认知微调Alpaca数据集指令监督微调断点续训 大模型微调 微调自我认知微调特定领域数据集。 平台&硬件 Ubuntu20.04显卡:M40 24G 2080TI 22G微调框架ÿ…...
git和github的使用指南
目录 1.git初始化本地仓库 2.远程仓库 3.如何将自己的代码上传到远程仓库的某一个分支 1.git初始化本地仓库 在项目目录中初始化 Git 仓库: cd your-project-directory git init 将文件添加到暂存区: git add . //添加所有文件 git add <fi…...
如何快速轻松地恢复未保存的 Word 文档:简短指南
文字处理器已经存在了几十年,其中许多已经变得非常擅长防止问题。丢失未保存的数据是一个常见问题,因此办公软件通常带有恢复文件的方法。在本文中,我们将介绍如何恢复 Word 文档,即使您尚未保存它。 确保数据安全的最佳方法是保…...
【Linux网络】打造初级网络计算器 - 从协议设计到服务实现
📢博客主页:https://blog.csdn.net/2301_779549673 📢博客仓库:https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! &…...
基于STM32定时器中断讲解(HAL库)
基于STM32定时器中断讲解(HAL库) 1、定时器简单介绍 以STM32F103C8T6中几个定时器为例: TIM1:这是一个高级定时器,不仅具备基本的定时中断功能,还拥有内外时钟源选择、输入捕获、输出比较、编码器接口以…...
《Vue3学习手记5》
pinia 共享的数据交给集中状态管理 引入与使用 //main.ts // 引入Pinia import {createPinia} from "pinia"const piniacreatePinia() app.use(pinia)案例: <template><div class"count"><h2>当前和为:{{ sum…...
MySQL多查询条件下深度分页性能优化技巧及示例总结
深度分页(Deep Pagination)是MySQL中常见的性能瓶颈问题,特别是在多查询条件下,当offset值很大时,查询性能会急剧下降。本文将总结多种优化技巧,并提供实际示例。 一、深度分页的性能问题分析 当执行类似SELECT * FROM table WHERE condition1 AND condition2 LIMIT 1000…...
3、初识RabbitMQ
界面上的导航栏共分6部分,分别代表不同的意思 一、Producer和Consumer Producer: 生产者, 是RabbitMQ Server的客户端, 向RabbitMQ发送消息 Consumer: 消费者, 也是RabbitMQ Server的客⼾端, 从RabbitMQ接收消息 Broker:其实就是RabbitMQ Server, 主要…...
量子计算与GPU的异构加速:基于CUDA Quantum的混合编程实践
一、量子模拟的算力困境与GPU破局 量子计算模拟面临指数级增长的资源需求:n个量子比特的态向量需要存储2^n个复数。当n>30时,单机内存已无法承载(1TB需求)。传统CPU模拟器(如Qiskit Aer)在n28时计算…...
在Spring Boot项目中实现Word转PDF并预览
在Spring Boot项目中实现Word转PDF并进行前端网页预览,你可以使用Apache POI来读取Word文件,iText或Apache PDFBox来生成PDF文件,然后通过Spring Boot控制器提供文件下载或预览链接。以下是一个示例实现步骤和代码: 1. 添加依赖 …...
Windows怎样使用curl下载文件
安装curl 从官网下载:访问curl官方网站,根据系统位数(32 位或 64 位)选择相应的版本进行下载。下载完成后,双击安装程序并按照提示进行安装。也可以选择自定义安装路径,记住安装路径,后续配置环…...
priority_queue的学习
priority_queue的介绍 优先级队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被…...
浅谈Java 内存管理:栈与堆,垃圾回收
在Java编程世界里,内存管理是一项极为关键的技能,它就像程序运行背后的“隐形守护者”,默默影响着程序的性能与稳定性。今天,咱们就来简单学习一下Java内存管理中的两大核心要点:栈与堆的内存分配机制,以及…...
windows下查看idea运行的进程占的JVM情况工具
jconsole 查看JVM 查看线程数 自己测试时,可以先不把线程关闭查效果。 也可以用这工具查下是不是有线程一直在增加。...
【新技术】微软 Azure Test Impact Analyzer (TIA) 全面解析
目录 一、什么是 Azure Test Impact Analyzer?二、核心功能与优势三、如何掌握 Azure TIA?四、工作中的典型应用场景五、最佳实践与注意事项六、总结 一、什么是 Azure Test Impact Analyzer? Azure Test Impact Analyzer (TIA) 是微软 Azur…...
JAVA服务内存缓慢上涨,年轻代GC正常但Full GC频繁,如何定位?
1. 分析 : 年轻代GC正常,说明年轻代的对象回收没有问题,可能大部分对象都是朝生夕死的,所以Minor GC能有效清理。但Full GC频繁,通常意味着老年代空间不足,导致频繁进行Full GC来回收老年代。而内存缓慢上…...
浏览器界面无显示,提示“代理服务器可能有问题”,这是怎么回事呢?
前言 🌟🌟本期讲解浏览器代理服务器解决办法介绍~~~ 🌈感兴趣的小伙伴看一看小编主页:GGBondlctrl-CSDN博客 🔥 你的点赞就是小编不断更新的最大动力 🎆那么废话不…...
C#中的弱引用使用
弱引用(Weak Reference)是一种特殊的引用类型,它允许你引用一个对象,但不会阻止该对象被垃圾回收器(GC)回收。弱引用通常用于需要缓存或跟踪对象,但又不希望因保留引用而导致内存泄漏的场景。弱…...
在Linux虚拟机下使用vscode,#include无法跳转问题
总结:需要通过Linux指令来添加编译器和压缩文件,解压,这样获得的编译器会具有可执行权限类似于 -rwxr-xr-x 1 user user 12345 Apr 26 14:22 myscript.sh 如果你直接从window中拖入文件到Linux文件下,你需要自己来再度开启可编译…...
MIL、SIL、HIL与Back-to-Back测试详解:从模型到硬件的完整验证链
1. 引言 在嵌入式系统和控制算法开发中,MIL、SIL、HIL和Back-to-Back测试构成了从模型设计到硬件部署的完整验证流程。它们覆盖不同开发阶段,确保系统功能正确性、实时性和可靠性。 本文将清晰解析这四种测试方法的核心概念、应用场景及差异。 2. 四种测…...
【Android Compose】焦点管理
官方文档链接: https://developer.android.google.cn/develop/ui/compose/touch-input/focus?hlzh-cn 1、更改焦点遍历顺序 1.1、替换一维遍历顺序 (1)创建焦点引用对象: /// 创建4个引用对象(二选一)…...
启动命令汇总(Redis / Kafka / Flume / Spark)
本文总结了本地开发环境(Windows系统)中启动推荐系统所需的所有组件命令,包括 Redis、Kafka、Flume 及 SparkStreaming 程序的启动流程。 1. 启动 Redis 进入 Redis 安装目录,执行: redis-server.exe测试连接&#x…...
python 画折线统计图
Python 画折线统计图(line chart)最常用的是 matplotlib。 最基本的折线图代码如下: import matplotlib.pyplot as plt# 假设这是你的数据 x [1, 2, 3, 4, 5] y [2, 3, 5, 7, 11]# 创建折线图 plt.plot(x, y, markero) # markero 是在点…...
java面向对象编程【高级篇】之继承
目录 🚀前言🤔什么是继承?🌟权限修饰符💯private 修饰符💯默认(无修饰符)💯protected 修饰符💯public 修饰符💯归纳 🦜继承的特点&…...
【数论分块】数论分块算法模板及真题
1.数论分块的含义 数论分块算法,就是枚举出使得取整函数发生变化的地方。 例如,对表达式 ⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor ⌊in⌋使用数论分块算法,就可以在 O ( n ) O(\sqrt n) O(n )的时间复杂度下枚举所有满足 ⌊ n i − 1 ⌋…...
DIY 3D打印机 原理及步骤概况
一、3D打印机的基本原理 硬件组成: 运动系统:控制X/Y/Z轴的步进电机(或直线电机),决定打印头的移动精度。 热端(挤出机):加热并挤出材料(如PLA、ABS塑料)。 …...
深度探索:DeepSeek赋能WPS图表绘制
一、研究背景 在当今数字化信息爆炸的时代,数据处理与可视化分析已成为众多领域研究和决策的关键环节。随着数据量的急剧增长和数据维度的不断丰富,传统的数据可视化工具在应对复杂数据时逐渐显露出局限性。Excel作为广泛应用的电子表格软件,…...
内存四区(栈)
今天我再次学到了有趣的知识,内存四区! 内存四区分为代码区,全局区,栈区,堆区,今天我们详细来讲讲栈区! 内存四区和栈区都是用来存放数据的,而栈区存放的数据具体有两类 1.形参数…...
Nginx性能优化:从配置到缓存,全面提升Web服务器性能
一、基础配置优化:释放硬件潜能 进程与连接调优 worker_processes: 推荐设置为 auto(自动匹配CPU核心数),但在特殊场景下需手动优化:worker_processes 8; # 8核CPU手动指定 worker_cpu_affinity 000…...
系统架构设计(三):质量属性
常见分类 一般来说,质量属性可以分为以下几类: 类别常见质量属性性能相关响应时间、吞吐量、资源利用率、实时性、可扩展性可用性相关可用性、高可用性(HA)、可靠性、容错性、恢复性可维护性相关可维护性、可测试性、可扩展性、…...
C#中常见的设计模式
文章目录 引言设计模式的分类创建型模式 (Creational Patterns)1. 单例模式 (Singleton)2. 工厂方法模式 (Factory Method)3. 抽象工厂模式 (Abstract Factory)4. 建造者模式 (Builder) 结构型模式 (Structural Patterns)5. 适配器模式 (Adapter)6. 装饰器模式 (Decorator)7. 外…...
C# 枚举(Enum)声明与使用详解
在 C# 编程中,枚举(Enum)是一种非常实用的数据类型,它允许你定义一组具有名称的整型常量,使代码更具可读性和可维护性。枚举可以有效地替代使用硬编码数值,尤其是在处理状态、选项或标志时。本文将深入探讨…...
Linux-进程控制
目录 一、进程创建 1.1、fork()函数 1.2、fork的返回值 1.3、写实拷贝(Copy-on-Write,COW) 1.4、fork常规用法 1.5、fork调用失败的原因 二、进程退出 三、进程等待 1、wait和waitpid 1.1、解决僵尸进程问题 1.2、status参数 程序正…...
【优选算法 | 滑动窗口】滑动窗口算法:高效处理子数组和子串问题
算法相关知识点可以通过点击以下链接进行学习一起加油!双指针 在本篇文章中,我们将深入剖析滑动窗口算法的核心原理。从基础概念到实战应用,带你了解如何利用滑动窗口高效解决连续子数组和子串等问题。无论你是算法入门的新手,还是…...
RabbitMQ全栈实践手册:从零搭建消息中间件到SpringAMQP高阶玩法
目录 前言 认识MQ 同步调用 异步调用 技术选型 安装 SpringAMQP 交换机类型 队列交换机绑定 环境搭建 Fanout交换机 声明队列和交换机 消息发送 消息接收 总结 Direct交换机 声明队列和交换机 消息发送 消息接收 总结 Topic交换机 声明队列和交换机 消息…...
头歌实训之存储过程、函数与触发器
🌟 各位看官好,我是maomi_9526! 🌍 种一棵树最好是十年前,其次是现在! 🚀 今天来学习C语言的相关知识。 👍 如果觉得这篇文章有帮助,欢迎您一键三连,分享给更…...
系统架构设计中的DSSA方法:理论、实践与行业深度应用
引言 在软件架构设计领域,DSSA(Domain-Specific Software Architecture,领域特定软件架构)是一种专注于垂直行业或业务领域的架构设计方法论。与通用架构设计不同,DSSA通过提炼领域共性需求、构建可复用资产库&am…...
设计心得——数据结构的意义
一、数据结构 在老一些的程序员中,可能都听说过,程序其实就是数据结构算法这种说法。它是由尼克劳斯维特在其著作《算法数据结构程序》中提出的,然后在一段时期内这种说法非常流行。这里不谈论其是否正确,只是通过这种提法&#…...
【C】初阶数据结构12 -- 冒泡排序
本篇文章主要讲解经典排序算法 -- 冒泡排序。 目录 1 算法思想 2 代码 3 时间复杂度与空间复杂度分析 1) 时间复杂度 2) 空间复杂度 1 算法思想 选择排序是一种经典的交换排序算法。其算法思想也比较简单,主要是比较相邻元素&…...
HTTP, AMQP, MQTT之间的区别和联系是什么?华为云如何适配?
目录 🔗 一、共同点(联系): 🔍 二、区别对比: 📘 三、简要说明 1. HTTP 2. AMQP 3. MQTT 🔗 四、三者联系(在华为云IoT平台中的应用) 🎯 …...
WPF之项目创建
文章目录 引言先决条件创建 WPF 项目步骤理解项目结构XAML 与 C# 代码隐藏第一个 "Hello, WPF!" 示例构建和运行应用程序总结相关学习资源 引言 Windows Presentation Foundation (WPF) 是 Microsoft 用于构建具有丰富用户界面的 Windows 桌面应用程序的现代框架。它…...
CrewAI Community Version(二)——Agent
目录 1. Agent总览2. Agent属性3. 创建Agent3.1 YAML配置3.2 直接用代码定义3.3 运行结果 参考 1. Agent总览 在CrewAI框架中,Agent是一个能具备下列能力的自主单元: 1. 执行特定的任务 2. 基于它的角色和目标进行决策 3. 使用工具完成任务 …...
阿里云VS AWS中国区:ICP备案全攻略与常见误区解析
导语 在中国大陆开展互联网服务时,ICP备案是必不可少的合规步骤。然而,随着云服务的多样化,许多企业在选择备案路径时常常感到困惑。本文将深入解析阿里云和AWS中国区的备案区别,为您提供清晰的操作指南,助您避开备案陷阱,确保业务合规运营。 一、备案基本原则 1. 服务器决定…...
基于libdxfrw库读取样条曲线并离散为点
在计算机辅助设计(CAD)与制造(CAM)领域,DXF(Drawing Exchange Format)格式文件被广泛用于存储与交换矢量图形信息。样条曲线作为DXF文件中常见的复杂曲线类型,其准确读取与离散化处理…...
学习 Apache Kafka
学习 Apache Kafka 是一个很好的选择,尤其是在实时数据流处理和大数据领域。以下是一个系统化的学习建议,帮助你从入门到进阶掌握 Kafka: 1. 先决条件 在开始 Kafka 之前,确保你具备以下基础: Java 基础:K…...
5.3/Q1,GBD数据库最新文章解读
文章题目:The burden and trend prediction of ischemic heart disease associated with lead exposure: Insights from the Global Burden of Disease study 2021 DOI:10.1186/s12940-025-01155-w 中文标题:与铅暴露相关的缺血性心脏病的负担…...