一、相交链表

相交链表
在这里插入图片描述

首先理解什么是链表相交，相交即存在共用的节点，链表相交有三种情况，

中间位置相交
头部就开始相交
尾部相交

在这里插入图片描述
如图pcurA和pcurB就都有一个next指针指向同一个节点
这几种链表结构画成图如下

为什么说链表中没有第一种结构呢？

相交点即一个节点，其包括两个组成部分，一个是存储的数据，一个是next指针，一个节点的next指针不可能同时指向两个节点

这里也可以总结出两个链表相交的条件：
两个链表的尾节点相同，两个链表一定相交

思路：求两个链表的长度，长链表先走长度差步，长短链表开始同步遍历，找相同的节点

在这里插入图片描述

return NULL把结果给远程服务器，会把结果包装一下，最后输出没有相交点

二、环形链表I

环形链表I
简单来说，如果链表带环，链表尾节点的next指针不会直接置为空，且遍历链表是一个死循环的
补充：环形链表的尾节点甚至可以指向自己
在这里插入图片描述

思路：快慢指针，慢指针每次走一步，快指针每次走两步，如果slow和fast指向同一节点，说明链表带环，类似于表盘的时钟和分钟

在这里插入图片描述

补充：快慢指针在一个链表上开始遍历，如果该链表不是带环的，那节点一定为空，这种链表又分为奇数和偶数情况

证明1：接下来最重要的部分来了，为什么在带环链表里面，慢指针每次走一步，快指针每次走两步，最终一定会相遇

在这里插入图片描述
图中slow的位置是入环点，入环之后是一个圆，其运动路径是一个圆。假设slow走到入环点，fast已经走到如图位置，此时slow和fast之间的距离最大，为N，此时slow走一步，fast走两步

二者之间距离变为N+1-2=N-1，继续就是N-2，N-3，如图最后变为0，也就是相遇，所以慢指针走一步，快指针走两步，如果是环形链表一定会相遇，就像表盘当中的时针和分针一样。

证明2：在环形链表中，慢指针每次走一步，快指针每次走3，4，5步，快慢指针在环形链表中还会相遇吗？

在这里插入图片描述
这里就以慢指针每次走一步，快指针每次走三步为例，依旧假设此时slow刚入环，此时slow和fast之间的距离最大，为N。
此时slow走一步，fast走三步，二者距离变为N+1-3=N-2。再一次就是N-2+1-3=N-4。

此时二者之间距离想要变为0，N必须要是偶数才行，这一圈才可以追上。若N为奇数（比如说N=7），7-2=5，5-2=3，3-2=1，1-2=-1。这一圈便追不上了
这样本来fast在追slow，二者距离变为-1，fast在slow前面，变为slow追fast。
当套圈之后，slow和fast的距离便变为了下图红线的长度，加入一圈的周长是C，套圈之后二者的距离便变为了C-1
在这里插入图片描述
在C-1的距离又要slow走一步，fast走三步，继续开始追逐

如果会相遇，说明在环形链表里面，fast走三步也能判断链表是否是带环的，反之

接下来就要证明C-1到底是奇数还是偶数
在这里插入图片描述
这是在第二圈开始追逐，这里fast的位置不代表fast第一圈入环之后到此处，slow就入环，在此之前fast可能已经走了好几圈，下图给出fast和slow的路程关系

由于快指针无论在圈里走几圈，都不影响其在圈里的位置，所以（n+1）可以忽略掉，就剩下C-N，前面明确的规定N是个奇数，所以C也一定为奇数。