LeetCode.141——环形链表：
题目如下：
通过题目中对于环形链表的大体描述，可以知道，环形链表最后一个结点保存了一个地址，用于返回链表中某个结点。并且。这个返回的结点并不是返回图中保存数据的结点。而是返回链表中任意一个结点。即：
或者：
题目中给了两个要求，分别是：
1. 判断链表中是否有环
2. 如果不存在环，则返回，存在环则返回。
对于不存在环的这种情况很好判断。如果链表中任意一个结点保存的地址为,则这个链表不带环。但是难点在于如何判断链表带环。如果按照判断不带环的思想去判断是否带环，即链表是否可以无限运行下去显然不可能。
如果采用双指针的方法一个指针从头结点开始，另一个指针向后遍历，如果存在则说明存在结点。否则就让指向下一个结点的方法，也不能实现目的。因为带环链表按照上面的方法进行遍历时，因为带环链表中不存在存储的结点。所以一旦开始遍历，也会造成死循环。
虽然上面给出的两种方法均不能解答题目。但是，第二种方法中，对比两个指针所指向的结点中保存的地址是否相等的思路是正确的。
在上一篇文章LeetCode——单链表相关题目（持续更新）_起床写代码啦！的博客-CSDN博客
中对于寻找链表中间结点时，用到了一个方法，及创建两个指针变量,，让 每次向后遍历个结点，每次向后遍历个结点。让两个指针变量所在链表中结点的位置形成一个差值。这个方法恰好可以用来解决本题。
为了方便后续进行画图演示，将环形链表用下方的图形进行表示：
其中表示这个链表的头结点，表示进入环的第一个结点。表示 ，这两个指针在环中相遇的结点。
将上面所提供的思路进行如下总结：
1.题目的两个要求中，返回的情况是不存在环，也就是说链表中有某个结点存储的地址为。对于返回，判断条件就是，这两个指针中存储的地址是同一个。所以，可以将解决题目的重点放在如何找到两个指针相遇的结点，也i就是。
2.对于如何寻找，前面给出了方法，创建不同的指针，每个指针每次向后遍历的结点数是不同的。如果遇到两个指针中存储的地址相等。则说明找到了。但是，对于上面给出的方法，会引出一个问题，即这两个指针在环形链表中是否会一定相遇的问题。下面将对这个问题进行探究
，这两个指针步数差为任意值时，是否一定会在环形链表中相遇（重点）：
按照文章上面所规定的：每次向后访问一个结点。每次向后访问两个结点，当恰好进入环的起始结点时，的位置大致如下：
当恰好位于环的起始位置时，的位置大致如下：
此时， 开始追赶。假设，两个指针中间的距离，即红线所标出的距离为。两个指针每向后按照自己的速度遍历一次，两个指针之间的距离就会缩短.所以，无论这个距离是奇数还是偶数。都可以找到这个结点，即两个指针指向的结点保存的地址相同。
在判断链表是否有环时，对于有环的链表，两个指针会一直按照规定运动下去。对于无环的链表，会存在结点数为奇数和结点数为偶数两种情况。下面给出不带环链表对于这两种情况下，循环是否执行的判定。
（注：上述推论只是局限于一个每次访问一个结点，一个每次访问两个结点的特殊情况。对于更加严格的推论会在本文下方LeetCode.142中详细展开）
对于结点数为奇数的情况下：
如图所示，当结点数量为奇数且这个奇数时，指针走完这个链表所需要的次数永远是偶数。所以对于结点数量为奇数的链表。指针每次向后访问，都有可能恰好访问到链表的最后一个结点。所以需要检测已经被访问的结点中存储地址是否为即可。即;
对于结点数为偶数的情况下：
如果像结点数为奇数的情况下去判断结点数量为偶数的链表，可以从图上看到，当结点数时，判定为是没有环的。当数量且为偶数时，每执行一次，后面总是会剩下一个结点。再向后执行一次，此时的为，所以，偶数结点的情况下，指针是有可能访问到的，因此只需要判定是否为空即可。
将上面的过程用代码表示，即：
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow -> next;
fast = fast -> next -> next;
if( slow == fast)
{
return true;
}
}
return false;
}执行结果如下：
LeetCode.142——环形链表Ⅱ：
(重点）探讨访问结点数不同的两个指针是否一定可以在环形链表中相遇：
如上图所示的一个环形链表，创建,两个指针，其中每次向后面访问一个结点。每次向后面访问三个结点。所以，两个指针每按照自己的速度向后进行一次访问，就会拉开两个结点的距离。当恰好走好环的起点，即：时，两个指针所在的位置差不多由下面的图来表示：
因为 的访问速度大于，所以，可以上图理解成一个追赶问题。将两个指针之间用红线画出的距离用表示。所以，两个指针同时运动一次，距离就会变成。
假设是一个偶数，则，两个指针同时追赶次后，二者之间的距离会变成，并且一定会出现距离为的情况，即两个指针同时在点。
假设为奇数，则，两个指针同时追赶次后，二者之间的距离会变成，但并不会出现二者之间距离为的情况。而是会出现的情况。即一个是慢于一个结点的距离，一个是快于一个结点的距离。对于的情况，可以由下面的图像表示：
假设，整个环的长度为，则图中用蓝色线所标出的两个指针之间的距离就变成。
假设， 为偶数，则会重复为偶数的情况。两个指针会相遇。
假设，为奇数，则会重复为奇数的情况。两个指针不会相遇，而是无限循环两个指针之间的距离为的情况。
假设每次向后访问一个结点，向后访问4个结点。两个指针同时向后访问，两个指针之间的距离差是个结点的长度。对于两个指针会不会相遇的问题，就需要分成%,%,%三个情况来谈论。方法与上面的类型，不再展开叙述。
前面说到，当每次向后访问一个结点，每次访问两个结点时，二者一定可以在环内相遇。又因为在相同的访问次数下所访问的结点，是的两倍。如果用距离来表示访问的结点的数量，上面的话也可以理解为，在相同的时间里，所走过的距离是走过距离的两倍。当二者恰好在相遇时，即：
用来表示头结点到环入口结点的距离，用表示环入口结点到的距离。
此时，指针所走过的距离可以表示为,指针所走过的距离可以表示为
。又因为上面说到，走过的距离是走过距离的两倍，所以
,化简后可得：。但是，如果当环的长度远小于时，本式不成立。此时：
若环的长度远小于时，当位于时，恰好位于环的起点。即：
当 恰好走到环的起点时，此时因为,所以，已经走过个，因此。当二者在相遇时，二至所走过的距离可以表示为：
化简后可得：
为了便于理解上述公式的含义，可以进一步化简为：
其中，根据上面给出的图像，可以得出上述公式所表达的含义，即：当一个指针一次访问一个结点，另一个指针一次访问两个结点的前提下，一个结点从头结点走到环入口点的距离，恰好等于另一个指针从点走向点的距离，即：一个指针从头指针出发，一个指针从点出发，二至一定会在点相遇。在解决这个题目时，将会用这个结论：
题目如下：
思路一：
题目要求返回入环的第一个结点，即返回上面图中的点。通过上面给出的结论。即：一个指针从头指针出发，一个指针从点出发，二至一定会在点相遇。可以得到解决题目的方法：
1. 找到两个指针在环中相遇的点。
2.让头指针和在点的同时向后遍历，二者相遇的那个点就是入环的第一个结点。
代码表示为：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head, *fast = head;
while( fast && fast -> next)
{
fast = fast -> next -> next;
slow = slow -> next;
if( slow == fast)//存在相遇点，两个指针相遇
{
struct ListNode* meet = slow;
while( head != meet)
{
meet = meet -> next;
head = head -> next;
}
return meet;
}
}
return NULL;
}执行结果如下：
思路二：
如果当两个指针在点相遇后，取，用来表示这个点。即后的一个点。并且让结点与后面的点断开链接，即：,此时的链表可以用下图表示：
再对上面的图片进行更改，即：
通过对图像的改进，可以题目改进为上篇文章LeetCode——单链表相关题目（持续更新）_起床写代码啦！的博客-CSDN博客 中的寻找相交结点问题。这里只给出代码，不过多解释：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA = headA,*curB = headB;
int lenA = 0,lenB = 0;
//计算headA为开头的链表的长度及最后的结点地址
while( curA -> next)
{
curA= curA -> next;
lenA++;
}
//计算headB为开头的链表的长度及最后的结点地址
while( curB -> next)
{
curB = curB -> next;
lenB++;
}
//检查两个链表最后一个结点的地址是否相等。相等则说明有交点
if( curA != curB)
{
return NULL;
}
//计算lenA和lenB的绝对值差值
int gap = abs( lenA - lenB);
//检查lenA和lenB哪个更长
struct ListNode* longlist,*shortlist;
if( lenA > lenB)
{
longlist = headA;
shortlist = headB;
}
else
{
longlist = headB;
shortlist = headA;
}
//longlist先走gap步
while( gap--)
{
longlist = longlist -> next;
}
//上下链表的起点位置没有结点数差，再一起遍历，寻找相交点
while( longlist != shortlist)
{
longlist = longlist -> next;
shortlist = shortlist -> next;
}
return longlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head, *fast = head;
while( fast && fast -> next)
{
fast = fast -> next -> next;
slow = slow -> next;
if( slow == fast)//存在相遇点，两个指针相遇
{
struct ListNode* meet = slow;
struct ListNode* newhead = meet->next;
meet->next = NULL;
return getIntersectionNode(newhead,head);
}
}
return NULL;
}
文章来源：https://www.toymoban.com/news/detail-692339.html
文章来源地址https://www.toymoban.com/news/detail-692339.html
到了这里，关于LeetCode.141,142——环形链表，环形链表Ⅱ的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【LeetCode】数据结构题解（5）[分割链表]](https://imgs.yssmx.com/Uploads/2024/02/444977-1.png)
![【LeetCode】数据结构题解（6）[回文链表]](https://imgs.yssmx.com/Uploads/2024/02/434983-1.png)
![【LeetCode】数据结构题解（9）[复制带随机指针的链表]](https://imgs.yssmx.com/Uploads/2024/02/672298-1.png)
