题解 | #链表中环的入口结点#

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 这说明两者相遇时，慢指针走过的非环部分，和快指针距离环入口处的距离是一致的

那么我们只需要求出相遇点，然后使用两个指针，一个从相遇点出发，一个从头节点出发，这两个节点相遇的节点就是入口地点了。