【数据结构】链表专题2

前言 本篇博客继续探讨有关链表的专题，这片博客的题，提前打个预防针，有点意思哦，哈哈哈，话不多说，进入正文 💓 个人主页：小张同学zkf ⏩ 文章专栏：数据结构 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章 ​

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，感谢观看！！！