前言

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

 个人主页:小张同学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,感谢观看!!!

相关文章

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。