Leetcode: 142. 环形链表 II —— 双指针法白话解读

哈希表的方法较为直观简单就不分享了，本题解采用双指针法，也是参考了别人和官方的题解才逐渐理解的，一开始对相关的公式推导其实并不太能理解，想了很久才懂。我在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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24