前言
本篇博客继续探讨有关链表的专题，这片博客的题，提前打个预防针，有点意思哦，哈哈哈，话不多说，进入正文
个人主页：小张同学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，感谢观看！！！
相关文章
发表评论