当前位置：首页 > news >正文

LeetCode带环链表题深度解析(是否带环、寻找环的入口结点)

news 来源：原创 2025/5/7 4:42:58

一、链表是否带环

常规方法解析：

拓展问题：那么fast一次走三步，走四步...是否还会相遇？

fast ：3 ，low ：1

fast ：4 ，low ：1

总结：

二、寻找带环链表的入环节点

前言：

链表带环问题时常出现在面试当中，考察对快慢指针以及情况分析的能力。对于链表是否有环，通常可以使用 fast ： 2 而 low ：1 的快慢指针来判断，不相遇即无环，相遇即有环。对于环的入口节点，则让一个指针从起始点出发，另一个指针从相遇点出发(按原方向)，以相同速度走，最终相遇于环的入口节点处。本文将深度解析，助力读者知其然并知其所以然。

一、链表是否带环

141. 环形链表 - 力扣（LeetCode）

解题方法：快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始走，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

深度解析：

常规方法解析：

由起始位置到入口节点位置的节点数为L，环状链表节点数为M。

假设low指针走到入口节点处，fast指针走到图示位置处，离low指针顺时针N个节点。

我们可知，fast只需要走M - N节点就可以追上low，由于fast每次走2个节点，而low每次走一个节点，那么每循环前进一次，fast与low的顺时针距离(M - N)就要缩短1(fast : 2 - low : 1)。

那么，在有限循环前进后，fast与low的顺时针距离(M - N)就要缩短为0，此时fast就会与low相遇。

拓展问题：那么fast一次走三步，走四步...是否还会相遇？

fast ：3 ，low ：1

有读者就说了，这有什么好解析的，在操场上绕圈跑步，跑得快的肯定可以追上跑的慢的喽，现实里是这样没错，但链表可能有些不同。我们来看：

由于代码:


for(int i = 0; i < 3; i++)
{fast = fast->next
}
low = low -> next;
if(fast == low) return true;
else
{...}

你很可能就会越过low，导致无法相遇，但真无法相遇了吗？

如今只有 M - N 为奇 && M - 1 为奇 则不会相遇，那么会出现这样的情况吗？？

由此我们可知，当fast ： 3，low ： 1时，同样可以相遇。

fast ：4 ，low ：1

同理：

分析到这，我们发现，是否能够相遇，与M - N的奇偶无关，与M - N是否为3的倍数有关，当有余数时，fast超过low后，fast与low顺时针距离就变成了M - 1或M - 2，那么是否可以由M - 1，M - 2来判断M的奇偶性呢？？

无法判断M的奇偶性，就无法判断N的奇偶性，就无法通过fast路程与low路程关系判断合理性。

所以当fast ：4 ， low ：1时，是否相遇与M的值有关，无法判断是否会相遇。

总结：

当fast的步数是一、二、三时，是可以确定一定会相遇的，但当步数超过三以后，就无法保证一定相遇，与环的节点数有关。

二、寻找带环链表的入环节点

142. 环形链表 II - 力扣（LeetCode）

解题方法: 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

假设fast指针与low指针于a点相遇,现将low指针移动链表起始位置处,两指针每步长都改为1。

这里为什么low的路程是L + N而没有多加？M呢？

解释：在上文判断链表带环时已经知道 fast 追 low 的最长顺时针距离应该为M - 1，就算他是M，假设low指针又转了一圈回到原位置，那么路程就为M，可是fast要比low快啊，fast路程一定大于low，所以一定可以在low走完一圈之前追上low。

注意，这里判断是否带环时是快慢指针，找入环节点时，快慢指针就已经变成同速指针了，所以才有当low走L步长时，fast由相遇点走？圈再走M - N步到达b点，也就是入环节点处。

一、链表是否带环

常规方法解析：

拓展问题：那么fast一次走三步，走四步...是否还会相遇？

fast ：3 ，low ：1

fast ：4 ，low ：1

总结：

二、寻找带环链表的入环节点

相关文章：