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

算法-链表-简单-相交、反转、回文、环形、合并

记录一下算法题的学习5

在写关于链表的题目之前,我们应该熟悉回忆一下链表的具体内容

什么是链表:

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。

怎么理解呢:是这样的:一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址(指针或引用)

链表的分类:

单向链表和双向链表

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

  单向链表的节点有两个属性 val,next; val是当前节点的值,next是指向下一节点的指针或引用

一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

 链表常用的方法:

public void add(int index, E element)向指定位置插入元素。
public void addFirst(E e)头插法
public void addLast(E e)尾插法
public void clear()清空链表
public E remove(int index)删除指定位置元素
public boolean contains(Object o)判断是否含有某个元素
public E get(int index)返回指定位置的元素
public E set(int index, E element)返回指定位置的元素
public Object[] toArray()返回一个由链表组成的数组
public int indexOf(Object o)查找指定元素从前往后第一次出现的索引。

 

算法leetCode简单题目(单向链表)

相交链表:

题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

代码与思路分析 

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//LinkNode是JAVA中链表结点//创建一个哈希集合 为什么用hashSet,不用list,一个是不可重复元素,一个是可重复元素,Set<ListNode> select=new HashSet<ListNode>();//遍历链表headA将链表A中每个节点都加入哈希集合中ListNode node=headA;while(node!=null){select.add(node);//假设这是第一次将第一个节点加入哈希集合中node=node.next;//自动变为下一节点值}//遍历链表B,判断遍历到的每个节点,判断该节点是否在哈希集合中ListNode temp=headB;while(temp!=null){//contains() 方法用于判断元素是否在哈希集合中if(select.contains(temp)){return temp;}temp=temp.next;//自动变为下一节点值,进行遍历判断}//如果链表headB中的所有节点都不在哈希集合中,则两个链表不相交,返回null;return null;}
}

反转链表:

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

代码与思路分析:

这个链表呢,是指向下一个节点的方向发生改变,使得链表发生了反转,下图便于理解分析:

 

 

class Solution {public ListNode reverseList(ListNode head) {ListNode original=head;//指向头结点ListNode end=null;  //指向null;//循环遍历使链表反转while(original!=null){ListNode temp=original.next; //使头结点的后继结点暂存,循环往复original.next=end; //改变next节点指向end=original;  //end暂存originaloriginal=temp;  //original往下一节点走}return end;}
}

回文链表:

题目:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

代码与思路分析:

首先我们要知道什么是回文即顺着看和倒着看是相同的

class Solution {public boolean  isPalindrome(ListNode head) {//我们的思路是将链表中的值复制到数组中,然后通过数组里使用左右双指针来判断是否回文//首先我们需要创建一个数组结构的集合,//使用单列集合Collection里的子接口List,它是有序且可重复元素List<Integer> vals=new ArrayList<Integer>();//其次将链表中的值复制到数组中,//单链表中的节点应该具有两个属性:val 和 next。// val 是当前节点的值,next 是指向下一个节点的指针/引用ListNode palindrome=head;while(palindrome!=null){vals.add(palindrome.val);//将回文链表中的每一个值复制到数组中,palindrome=palindrome.next;//指向下一个节点的指针/引用}//最后使用双指针判断是否回文int left=0; //List第一个元素的索引int right=vals.size()-1; //List最后一个元素的索引while(left<right){//两边发现值不相等,返回falseif (!vals.get(left).equals(vals.get(right))) {return false;}left++;right--;}//将元素全部跑一边,顺着和倒着是相同的,返回truereturn true;}
}

环形链表:

题目:

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

代码与思路分析:

我们重新作图使它更加直观:

 

 存储访问过的节点3 ,2,0,-4,然后我们又遇到了2这个节点,这个节点已经在哈希表中,所以证明该链表是一个环形链表。

public class Solution {public boolean hasCycle(ListNode head) {//首先创建一个哈希表,存储所有访问过的节点Set<ListNode>  node = new HashSet<ListNode>();//每当我们到达一个节点时,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中while(head!=null){if(!node.add(head)){return true;}//下一节点变化head=head.next;}//最后遍历完整个链表,发现不是环形链表,返回false;return false;}
}

合并两个有序链表:

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

代码与思路分析:

如果 list1 或者 list2 本身就是空链表 ,那么我们就不需要合并,我们只需要返回非空链表。如果两个链表有一个为空,递归结束,因为另一个链表本身就是有序的。如果 list1 和 list2 都不是空链表,就要 判断 list1 和list2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到新链表里的节点。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//首先判断链表list1和链表list2是否是空联表,如果都是空的,返回就是[];if(list1==null){return list2;}if (list2==null){return list1;}//然后从最初开始的两个链表的头结点的值进行比较,哪个小,就排第一位,//紧接着有了合并链表的头结点之后,我们找该头结点的下一节点值。//这里就看list1和list2哪个链表的头结点先判断出来,然后使它成为新的合并有序链表之后的新链表if(list1.val<list2.val){list1.next=mergeTwoLists(list1.next,list2);return list1;}else{list2.next=mergeTwoLists(list1,list2.next);return list2;}}
}

结语:

链表的简单学习到此结束!

相关文章:

算法-链表-简单-相交、反转、回文、环形、合并

记录一下算法题的学习5 在写关于链表的题目之前&#xff0c;我们应该熟悉回忆一下链表的具体内容 什么是链表&#xff1a; 链表&#xff08;Linked list&#xff09;是一种常见的基础数据结构&#xff0c;是一种线性表&#xff0c;但是并不会按线性的顺序存储数据&#xff0c…...

【500强 Kubernetes 课程】第3章 运行docker容器

一 - 三 &#xff0c;docker基础操作见 第2章7节 四、docker部署web网站 1、安装 nginx &#xff08;适合场景&#xff1a;学习 - 略&#xff09; 2、docker 安装 nginx Stage 1 &#xff1a;docker hub 上 搜索 nginx 镜像 Stage 2&#xff1a;拉取官方镜像 Stage 3&…...

Python中表格插件Tabulate的用法

目录 一、引言 二、Tabulate插件安装与导入 三、Tabulate基本用法 1、创建表格&#xff1a; 2. 格式化表格&#xff1a; 3. 表格转置&#xff1a; 4、合并单元格&#xff1a; 5、指定每列的格式&#xff1a; 6、指定每行的格式&#xff1a; 7、使用自定义表格格式&am…...

缺陷分级(过程质量bug分级)

缺陷按照其影响的严重程度&#xff0c;从高到低分成5级&#xff0c;分别为致命&#xff08;Blocker&#xff09;、严重&#xff08;Critical&#xff09;、一般&#xff08;Major&#xff09;、轻微&#xff08;Minor&#xff09;以及建议&#xff08;Enhancement&#xff09;。…...

pycharm/vscode 配置black和isort

Pycharm blackd Pycharm中有插件可以实现后台服务运行black&#xff1a;BlackConnect 安装 在python中安装blackd 配置 Pycharm isort pycharm中&#xff0c;isort没有插件&#xff0c;暂使用外部工具实现&#xff0c;外部工具也可添加快捷键实现快捷对文件、文件夹进行fo…...

python列出本地文件路径

按照之前的设想&#xff0c;如果要罗列出本地文件的列表&#xff0c;那不是需要不断的判断文件夹里面的文件夹吗&#xff1f;或者需要使用递归函数本身&#xff0c;才能达到目的吧&#xff1f;没想到使用pop这个函数就可以了。pop是取出元素&#xff0c;那列表里就少了一个&…...

在JavaScript中检查一个数字是否是另一个数字的倍数

使用%模数运算符 为了检查一个数字是否是另一个数字的倍数&#xff0c;我们可以使用JavaScript中的% modulo运算符。 modulo% 操作符返回第一个数字在第二个数字上的余数&#xff0c;例如&#xff1a;10 % 2 0 &#xff0c;所以如果我们得到一个余数0 &#xff0c;那么给定的数…...

计算机网络五层协议的体系结构

计算机网络中两个端系统之间的通信太复杂&#xff0c;因此把需要问题分而治之&#xff0c;通过把一次通信过程中涉及的所有问题分层归类来进行研究和处理 体系结构是抽象的&#xff0c;实现是真正在运行的软件和硬件 1.实体、协议、服务和服务访问点 协议必须把所有不利条件和…...

MySQL 运算符二

逻辑运算符 逻辑运算符用来判断表达式的真假。如果表达式是真&#xff0c;结果返回 1。如果表达式是假&#xff0c;结果返回 0。 运算符号作用NOT 或 !逻辑非AND逻辑与OR逻辑或XOR逻辑异或 1、与 mysql> select 2 and 0; --------- | 2 and 0 | --------- | 0 | -…...

【SA8295P 源码分析】121 - MAX9295A 加串器芯片手册分析 及初始化参数分析

【SA8295P 源码分析】121 - MAX9295A 加串器芯片手册分析 及初始化参数分析 一、MAX9295A 芯片特性1.1 GPIO 引脚说明1.2 功能模块框图1.3 时序分析1.3.1 GMSL2 Lock Time:25 ms1.3.2 视频初始化延时:1.1ms + 17000 x t(PCLK)1.3.3 High-Speed Data Transmission in Bursts1.…...

问题汇总20231103

文章目录 前言问题汇总1.所有操作系统在CPU层面上是不是都为时间片轮转的形式处理程序&#xff1f;只是任务调度的调度算法不同&#xff1f;那多线程的本质也是时间片吗&#xff1f;只不过很小&#xff1f;2.Mcu和mpu的本质区别3.下载HAL库步骤4.RAM,ROM,SRAM,SDRAM,DDR内存5.编…...

65.Undertow代替Tomcat

SpringBoot中我们既可以使用Tomcat作为Http服务&#xff0c;也可以用Undertow来代替。Undertow在高并发业务场景中&#xff0c;性能优于Tomcat。所以&#xff0c;如果我们的系统是高并发请求&#xff0c;不妨使用一下Undertow&#xff0c;你会发现你的系统性能会得到很大的提升…...

前端mockjs使用方式[express-mockjs]

前提 现在基本上都是前后端分离项目的开发&#xff0c;而前端对于UI界面开发完毕之后往往都需要等待后端的接口提供&#xff0c;因此为了解决这个问题&#xff0c;这里提供一个由express和mockjs结合的本地服务应用项目&#xff0c;可以前端随意造数据配合UI页面进行开发。 个…...

矿区安全检查VR模拟仿真培训系统更全面、生动有效

矿山企业岗位基数大&#xff0c;生产过程中会持续有新入矿的施工人员及不定期接待的参观人员&#xff0c;下井安全须知培训需求量大。传统实景拍摄的视频剪辑表达方式有限&#xff0c;拍摄机位受限&#xff0c;难以生动表达安全须知的内容&#xff0c;且井下现场拍摄光线不理想…...

在SpringBoot中使用EhCache缓存

在使用EhCache缓存之前&#xff0c;我们需要了解的是EhCache缓存是啥&#xff1f; Ehcache的概述 Ehcache是一个开源的Java缓存框架&#xff0c;用于提供高效的内存缓存解决方案&#xff0c;他可以用于缓存各种类型的数据&#xff0c;包括对象&#xff0c;查询结果&#xff0…...

filter - 常用滤镜效果(毛玻璃、图片阴影、图片褪色)

文章目录 filter 属性滤镜算法函数blur&#xff1a;高斯模糊hue-rotate&#xff1a;色相环contrast&#xff1a;对比度grayscale&#xff1a;灰度drop-shadow&#xff1a;图片阴影 常见的滤镜效果图片内容轮廓阴影毛玻璃图片黑白调整图片色相和对比度使元素或文字变圆润 filter…...

【开源】基于Vue和SpringBoot的数据可视化的智慧河南大屏

项目编号&#xff1a; S 059 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S059&#xff0c;文末获取源码。} 项目编号&#xff1a;S059&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 数据模块 …...

小型内衣洗衣机什么牌子好?性价比高的迷你洗衣机推荐

现在洗内衣内裤也是一件较麻烦的事情了&#xff0c;在清洗过程中还要用热水杀菌&#xff0c;还要确保洗衣液是否有冲洗干净&#xff0c;还要防止细菌的滋生等等&#xff0c;所以入手一款小型的烘洗全套的内衣洗衣机是非常有必要的&#xff0c;专门的内衣洗衣机可以最大程度减少…...

SIMULIA 2023 PowerFLOW 新功能介绍

PowerFLOW 2022仿真驱动设计 PowerFLOW2022重点关注MODSIM&#xff08;MODeling and SIMulation&#xff09;。新功能包括与3DEXPERIENCE平台上的CAD产品设计保持一致并从中无缝过渡&#xff0c;高度复杂的几何图形与间隙和孔的快速网格化以及过程自动化&#xff0c;初代 GPU求…...

智慧农业新篇章:拓世法宝AI智能直播一体机助力乡村振兴与农业可持续发展

随着乡村振兴战略的深入推进&#xff0c;农业发展日益成为国家关注的焦点。在这一大背景下&#xff0c;助农项目的兴起成为支持乡村振兴的一项重要举措。 乡村振兴战略的实施&#xff0c;得益于《关于推动文化产业赋能乡村振兴的意见》、《关于全面推进乡村振兴加快农业农村现…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...

k8s从入门到放弃之Pod的容器探针检测

k8s从入门到放弃之Pod的容器探针检测 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;容器探测是指kubelet对容器执行定期诊断的过程&#xff0c;以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...