【数据结构】链表专题2

devtools/2024/10/18 17:26:39/

前言

本篇博客继续探讨有关链表的专题,这片博客的题,提前打个预防针,有点意思哦,哈哈哈,话不多说,进入正文

💓 个人主页:小张同学zkf

⏩ 文章专栏:数据结构

 若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章 ​

目录

1.返回倒数第几个节点

2.链表的回文结构

3.相交链表


1.返回倒数第几个节点

这道题跟我们上一篇博客有道题返回中间节点有点像,首先这道题时间复杂度O(1),所以我们遍历原链表只能遍历一次

那我们就继续用返回中点节点的方法,快慢指针做这道题也适用

快慢指针,如若我让快指针先走k步,走完了再让慢指针走,此刻快慢指针就差k,双指针同时遍历,直到快指针走完,此刻慢指针返回的就是倒数第k的节点,所以一定要确保俩指针要差k

代码如下: 


2.链表的回文结构

这道题,我们乍一看有点难,要求时间复杂度为O(n),空间复杂度为O(1)

我们要想证明它是个回文结构,首先我们先了解回文结构的特征,就是以中间节点为中心,这个链表的值是对陈的,那我们要证明对称,我么是不是可以先找到终点节点,再反向一下以中间节点为首的之后的节点,然后中间指针与首指针遍历判断值是否相等,如图所示,这里有人有疑问,偶数个接点还可以看,但奇数个接点那,如图所示那个三,其实,再反转时,我们没有消除第一个二指向三的指针,所以两个2此刻都指向三, 只要在遍历时发生不相等的,那就不是回文,若直到遍历完,还都是相等的,那就是回文。

所以我们就创建两个函数,其实就把我们链表1里面的反转链表和返回中间节点的代码复制过来就行,哈哈,cv工程师

 那这两个函数我就不详细说了,在我的博客链表专题1里有,一个是反转链表用三指针法,一个是返回中间节点用快慢指针法

链表专题一博客链接:http://t.csdnimg.cn/zM8BB

好了整体总结一下

1.创建返回中间节点函数

2.创建反向链表函数,返回头结点

3.遍历原链表与函数返回的链表判断

代码如下: 


3.相交链表 

首先我们要想一点,什么是链表相交

首先看一个图 

这种可不是链表的相交

这种是

也就是说链表相交,是两个线合成一个线 

为什么这种不可以,因为链表一个节点怎么可能会同时指向两个节点,一个节点只能指向一个节点

所以这道题做法就清楚了

我们首先判断是否相交,若相交,其次返回相交的第一个节点

怎么判断相交那

有一个非常巧妙的方法

看俩链表是否尾结点一样,若一样,代表相交,否则不想交,我们仔细想想若俩链表合二为1,那么俩链表是不是就是同一个尾结点,所以这点很巧妙

注意这里尾结点判断是地址判断,不是值,值的话有可能出现俩链表尾结点值一样。

所以遍历俩链表找到最后一个节点就行了。 

 ok,我们判断完了,若相交,来继续看看怎么返回头结点

我们用俩指针指向两链表的头部,因为相交之前,俩链表的长度不确定,我们先判断,谁长,让谁先走他们相差的部分,走完另一个指针再遍历,此刻两个指针同时向后遍历,若遍历的值相同了,就找到第一个相交的节点了

OK,我们可以用假设法来判断

什么叫假设法?

 我们可以先创建一个变量来记录长的节点,另一个变量记录短的节点,然后假设长的就是第一个链表,短的就是第二个链表,再用if判断看两个变量需不需要互换,这样就不用管到底哪个链表长,哪个链表

假设法代码如下:

判断完之后就可以,让谁先遍历差值,再一起遍历,一个一个判断是否相等就行了

这道题代码如下


结束语 

链表专题2就结束了,还有几道典型的链表专题就放在下片博客说了

OK,感谢观看!!!


http://www.ppmy.cn/devtools/33404.html

相关文章

BL124网关支持Modbus转Ethernet/IP

Modbus网关BL120是一款专注于Modbus协议之间相互转换的通信设备。Modbus网关BL120支持多种下行采集协议,包括Modbus RTU和Modbus TCP,同时在上行转发协议方面同样支持Modbus RTU和Modbus TCP。Modbus网关为Modbus RTU和Modbus TCP协议的相互转换提供了稳…

element-ui的bug记录

1.先隐藏元素再显示元素时&#xff0c;导致校验不生效的做法 <el-form-itemlabel"时间长度"prop"timeLength"v-show"form.majorFlag":rules"[{ required: form.majorFlag ? true : false, message: 时间长度不能为空, trigger: blur }…

Unity之ShaderGraph入门简介与配置

前言 ShaderGraph是Unity的一个可视化着色器编辑工具,它允许开发者在不编写代码的情况下创建复杂的着色器效果。ShaderGraph提供了一个直观的图形界面,用户可以通过拖拽节点并连接它们来构建自定义的着色器。用户可以在ShaderGraph中使用各种节点,如数学运算、纹理采样、颜…

Golang | Leetcode Golang题解之第70题爬楼梯

题目&#xff1a; 题解&#xff1a; func climbStairs(n int) int {sqrt5 : math.Sqrt(5)pow1 : math.Pow((1sqrt5)/2, float64(n1))pow2 : math.Pow((1-sqrt5)/2, float64(n1))return int(math.Round((pow1 - pow2) / sqrt5)) }

第20天 多线程

多线程 cpu一次只能处理一条指令&#xff0c;所谓同时是因为人反应不过来 分为多个时间片段&#xff0c;尽可能平均分配给每一个线程 线程的创建 &#xff1a; 第1种方法&#xff1a;继承thread并重写run方法 psvm{ Thread t1 new MyThread1(); Thread t2 new MyThread2()…

【通信原理二】第八章 信道及信道编码

在上一章中&#xff0c;我们讨论过信源以及信源编码&#xff0c;本章节介绍了信道以及信道编码&#xff0c;主要介绍信道输入输出的数学关系——信道模型&#xff08;channel model&#xff09;以及信道最高能实现的传输速率——信道容量&#xff08;channel capability&#x…

知识图谱与大语言模型的协同(RAG)——MindMap

MindMap : Knowledge Graph Prompting Sparks Graph of Thoughts in Large Language Models 论文地址: https://arxiv.org/abs/2308.09729 代码:https://github.com/wylwilling/MindMap 1.概述 大型语言模型(LLMs)在处理新信息、防止生成幻觉内容、以及增强决策过程透明度…

typescript 对象数组和函数

typescript 对象数组和函数 对象 在JavaScript中&#xff0c;对象属于非原始类型。对象也是一种符合数组类型&#xff0c;由若干个对象属性构成。对象属性可以是任意数据类型&#xff0c;比如数组&#xff0c;函数或者对象等。当对象属性为函数的时候&#xff0c;称为方法。 …