环形链表II
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环
思路
题目要求
- 给定一个单链表的头节点，判断该链表是否存在环
- 返回环的入口
两个操作
- 判断是否有环
- 如果有环，如何找到环的入口
双指针法判断是否有环：
每次slow走一步，fast走两步。若无环，则两指针间距每次+1，fast最终为nil；若有环，则fast最终会追上slow，两个指针最终会在环中某节点相遇。
双指针法找环的入口：
此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。
假设从头结点到环形入口节点的节点数为x。 环形入口节点到fast指针与slow指针相遇节点的节点数为y。 从相遇节点再到环形入口节点的节点数为 z。 如图所示：
相遇时：
- slow指针走过的节点数为:
x + y， - fast指针走过的节点数：
x + n (y + z) + y， n为fast指针在环内走了n圈才遇到slow指针，(y+z)为一圈内节点的个数。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以fast指针走过的节点数 = slow指针走过的节点数* 2得(x + y) * 2 = x + y + n (y + z)，两边消掉一个(x+y)得x + y = n (y + z)。因为要找环形的入口，那么要求的是x，x = n (y + z) - y。再从n(y+z)中提出一个(y+z)，整理公式之后得x = (n - 1) (y + z) + z注意这里n ≥ 1的，因为fast指针至少要多走一圈才能相遇slow指针。
这个公式的意义：
- 当
n=1时，公式为 x = z。意味着fast指针在环形里转了一圈之后，就遇到了slow指针了。
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点!
- 当
n＞1时，意味着fast指针在环内转n圈之后才遇到slow指针。
其实这种情况和n=1的效果是一样的，一样可以通过双指针法找到环形的入口节点，只不过index1指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
动画如下：
解题思路来自：代码随想录
代码
Go
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { slowIndex, fastIndex := head, head for fastIndex != nil && fastIndex.Next != nil { slowIndex = slowIndex.Next fastIndex = fastIndex.Next.Next // 找到环 if slowIndex == fastIndex { index1 := fastIndex index2 := head // 找环的入口 for index1 != index2 { index1 = index1.Next index2 = index2.Next } return index1 } } return nil }
