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

package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	fast, slow := pHead, pHead
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		// 说明有环
		if slow == fast {
			break
		}
	}

	// 无环
	if fast == nil || fast.Next == nil {
		return nil
	}

	// slow 和 fast 相遇
	// 假设 slow 走了 k 步，即 起点 到 相遇点 为 k， fast 一定走了 2k 步
	// 环入口 与 相遇点 距离设为 m，则有 (相遇点 到 环入口 为 k - m ) == (起点 到 环入口 k - m)
	// 此时分别从 起点 和 相遇点 同时出发， slow 和 fast 以相同的速度走 k - m 即可到达入口
	slow = pHead
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}

	return slow
}