【剑指算法NO.01】141.环形链表

快慢指针

当我们需要遍历线性表的时候，比较常用的一个算法就是「双指针」。

双指针有两种：

1. 快慢指针；
2. 对撞指针（左右指针）

这里重点记录快慢指针在环形链表中的应用。

我们可以使用快慢指针判断链表中是否有环、同时也可以利用快慢指针在环中移动规律得到环的入口点。

判断是否有环的关键点：

快指针每次走两步、慢指针每次走一步，如果能相遇就说明有环。

如下图：

此时，慢指针已经进入环中了（蓝色块在黄色球上），两人都开始在环中沿着顺时针运动，快慢指针接下来的循环运动就成了追赶运动了

快慢指针相遇原因：

快指针会一直追赶慢指针，但是快指针比慢指针走的步数多，所以慢指针入环之后，接下来每循环一次，两个指针的相对距离都会减少一步。

这是因为，按照相对运动来说，快指针每次都比慢指针多走一步，我们假设慢指针没有运动、则快指针每次都走了一步。

而如图中，快指针在7、慢指针在4，如果慢指针一直站在入环口不动、快指针每次走一步，则快指针再走三步就能和慢指针团聚。

这个三步是怎么得来的呢？我们接着往下看：

总结规律就是：

在慢指针进入环中的那一刻起（4的位置），快指针已经走到了换的某个地方。

沿着顺时针的顺序计算：

快指针到慢指针之间的距离是x步、快指针就还差x步和慢指针汇合，循环就还需要x次。

这个x也就是 快指针 到环的入口（4）那里的结点的个数。

汇合点计算

现在我们不让慢指针站着不动，他还是一次走1步、快指针一次赶2步。我们来计算他们的汇合点。

当慢指针刚好进入 入环口 的那一刻起：

• 慢指针距离头结点是A
• 快指针距离头结点是2A、离开入环口的距离是A（因为2倍）
• 快指针离开入环口的距离是2A - A = A
• 设环的长度是L
  
  

如果快指针依旧每次走2步、慢指针走1步，那么快慢指针相遇的距离就是L -（L-A） = A（从入环口再加A的距离），也就是快慢指针相遇的位置就是头结点到入环口的距离。

分步模拟

接下来我们从慢指针入环开始，分步看看快慢指针何时相遇：

1、慢指针走1步到5的位置、快指针走2步到9的位置：

2、慢指针走1步到6的位置、快指针走2步到5的位置：

3、慢指针走1步到7的位置、快指针走2步到7的位置：俩人终于相遇了！

而他们的相遇，也就说明了，链表中有 环 的存在。

这就好比恋爱中的两个人，一个人成长快、一个人成长慢。成长快的先走了、成长慢的在后边慢慢追。

• 如果最终两人相遇了，说明命运有轮回。
• 如果成长慢的追到了生命的尽头（遇到了null）还没再次遇到成长快的，则说明二人此生不会再见、生命无轮回。（其实代码逻辑中，直接判断快指针有没有遇到null就行了，毕竟成长快的都死了，成长慢的也不可能再见到他了。）

神不神奇。

代码

纸上谈兵终觉浅，知道了思路，我们就来写一下代码。

力扣题目：141.环形链表

快慢指针实现方案：

另外我们也可以使用哈希表的方法，来降低时间复杂度。

简单思考来说，就是要遍历一遍链表，每次遍历都记下来结点，下次遍历时看看这个结点是否遇到过，如果遇到就说明有环：