题解 | #链表中环的入口结点#
链表中环的入口结点
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
slow, fast := pHead, pHead
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
index1, index2 := pHead, slow
for index1 != index2 {
index1 = index1.Next
index2 = index2.Next
}
return index1
}
}
return nil
}
同样使用快慢指针的思路，如果链表中有环，快慢指针一定相遇（快指针每次走两步，慢指针每次走一步，根据物理学上的相对运动，相当于慢指针不动，快指针每次移动一个位置去追赶慢指针，一定可以追得上）
假设两者相遇时，慢指针在非环部分（环入口节点 3 之前的部分）走了距离 x，在环中走的距离为 y；
快指针在非环部分走的也是 x，而在环的部分走了 y + n(y+z) 的距离，其中 y + z 是环的长度，n 表示在相遇之前快指针走的圈数；
快指针每次走两步，所以可以得到这个公式：x+y+n(y+z) = 2(x+y)
移项化简：
x+y+y+z+(n-1)(y+z) = 2x + 2y
x = z + (n-1)(y+z)
y+z 是环的长度，无论快指针绕了多少圈，真正起到相遇作用的还是 z
x = z 这说明两者相遇时，慢指针走过的非环部分，和快指针距离环入口处的距离是一致的
那么我们只需要求出相遇点，然后使用两个指针，一个从相遇点出发，一个从头节点出发，这两个节点相遇的节点就是入口地点了。
你只是陷入了短暂的低谷，你也一直有退路