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

// 两种方法；一种O(n)空间复杂度；记录每个节点是否被遍历过
// 另外一种；快慢指针; 存在环的话快慢指针一定会在环中相遇；相遇之后从这个点和开始节点出发；一次一步一定会在入口处相遇
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	if pHead == nil || pHead.Next == nil {
		return nil //空节点或者单个节点不存在环
	}
	slow, fast := pHead, pHead
	for fast != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { //快慢指针相遇；说明存在环，下一步就是把环的入口节点找出来
			fast = pHead
			for fast != slow {
				fast = fast.Next
				slow = slow.Next
			}
			//最终相遇的点就是入口节点
			return fast
		}
	}
	return nil
}