Leetcode: 142. 环形链表 II —— 双指针法白话解读
解题方法Code
哈希表的方法较为直观简单就不分享了，本题解采用双指针法，也是参考了别人和官方的题解才逐渐理解的，一开始对相关的公式推导其实并不太能理解，想了很久才懂。我在leetcode也发了自己的理解过程（还是个菜鸡，Leetcode名：nazarite-ascetic。)
解题方法
（1） 定义fast、slow，每次循环fast走两个节点，slow走一个节点。
（2）这里有个至关重要的分析，涉及到后面对两个基本问题的理解:
① “如果有环，这两个指针必定环内相遇” ② “slow入环的一圈之内必定与fast相遇”
一开始看到很多人说用“参考系”或“相对”的概念的去理解的时候，其实感觉自己似乎是能理解了，但是总感觉很模糊，其实并没有真正理解。（或许是自己不够聪明吧哈哈） 所以我决定自己去思考这是为什么，分析如下：
① fast比slow快，有环的情况下，fast必定比slow先入环，由于速度快，等slow入环之后，可以看作是fast在追赶slow
② 由于每次循环fast走两步，slow走一步，可以将fast两步的作用进行分解： 第一步用于抵消slow“逃离fast”的距离。 第二步会导致每次循环fast都会跟slow的距离缩小一步。 所以，总体上看必定能相遇而不是跳过。
接着，入环后，由于每次循环总体上看fast是一步一步接近slow的，而fast要追上slow的距离不会超过一圈的周长（如下图绿线所示），所以在slow走完自己的一圈之前，必定能让fast追上 （如果slow走完了第一圈，那么意味着循环了一圈的节点数量的次数，fast的“第二步”也等于一圈，两者距离小于一圈，所以必不可能一圈后才追上）
目前这两个基本问题应该是没有疑问的了
① “如果有环，这两个指针必定环内相遇” ② “slow入环的一圈之内必定与fast相遇”
（3）定义一个头结点指针的副本p，让slow指针在相遇点继续移动，p也同步移动，两个指针都是每次循环移动一步，再次相遇的地方，就是环的入口点了（这个我想不到，但是可以去试着理解证明过程，当做一个数学模型积累下来） 证明过程如下： ① a是头结点到环入口点的节点数（不含头结点），b是快慢指针相遇点到入口点的距离（不含相遇点），c是入口点到相遇点的距离（不含入口点）。总之就一句话，站在哪里就不包含哪个节点，因为是从那里出发的，就好像坐地铁时候还有几个站的计算一样
② slow和fast相遇时候可知：
③ 由于slow和fast是同步更新的，fast速度是slow两倍，所以直至相遇，fast走过的节点数是slow的两倍，所以推理出关系式： a+c+k(b+c) = 2(a+c) 由于题目求的是环的入口，所以合并同类项后，将a单独放在一边，就变成了：
a = k(b+c)-c = (k-1)(b+c) + b
对于上述公式，k等于多少跟a、b、c都有关系。 其实有了上述公式，就可以求得环入口点了。具体解释如下： 设置一个头结点副本res，让还在相遇点处的slow同步进行移动，两者相遇之处就是入口点。
相遇时，res指针走过的节点数就是a， slow指针走过的节点数就(k-1)(b+c) + b，也就是从相遇点出发，走过了b个节点后，再循环(k-1)圈，k-1当做一个整数看待就好
至此，原理已解释完毕，代码如下
Code
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
fast,slow := head,head
for fast != nil && fast.Next != nil { // 判断有没有环
slow = slow.Next
fast = fast.Next.Next
if fast == slow { // 有环
for res := head; res != slow && slow != nil; { // 找环开始点
res = res.Next
slow = slow.Next
}
return slow
}
}
return nil
}
精彩内容
您阅读本篇文章共花了：
发表评论