7.14 链表中环的入口地址

题目

如果一个链表中包含环，如何找出环的入口节点？

思路

1. 确定链表是否包含环，使用快慢指针，若链表存在环，必定有相遇的时刻

2. 找到环的入口，关键在于，当快慢指针相遇时，快指针走的路程刚好比慢指针走多一圈

   所以只要 另快指针先走环内节点数n 步，然后和慢指针同样速度向前移动，则它们将相遇在环的入口处

3. 因此需要获得 环中节点数， 可以通过在第一步中计数快慢指针走过的节点数，根据 2 ， 快指针走过的路程 - 慢指针走过的路程 = 环内节点数

实现代码

package LoopInTheList

type Node struct {
	Val int
	Next *Node
}



func LoopInList(list *Node) *Node {
	if list == nil {
		return nil
	}

	slowPtr := list
	fastPtr := list

	slowCounter := 0
	fastCounter := 0

	nodeNumInLoop := 0
	for true  {
		// no loop exist
		if fastPtr.Next == nil {
			return nil
		}
		fastPtr = fastPtr.Next
		if fastPtr.Next == nil {
			return nil
		}
		fastPtr = fastPtr.Next
		fastCounter+=2

		slowPtr = slowPtr.Next
		slowCounter++

		// meeting loop exist
		if slowPtr == fastPtr {
			nodeNumInLoop = fastCounter - slowCounter
			break
		}
	}

	//reset
	slowPtr = list
	fastPtr = list
	// let fastptr go nodeNumInLoop
	for i:=0 ; i< nodeNumInLoop ; i++{
		if fastPtr.Next == nil{
			return nil
		}
		fastPtr = fastPtr.Next
	}

	for true{
		//find entry node
		if slowPtr == fastPtr {
			return slowPtr
		}

		if fastPtr.Next == nil{
			return nil
		}
		slowPtr = slowPtr.Next
		fastPtr = fastPtr.Next
	}
	return nil
}