写在前面

判断一个链表是否有环比较容易，但是要找出环的入口并不容易。

单链表环相关的考题很多，比如：

给一个单链表，判断其中是否有环的存在；
如果存在环，找出环的入口点；
如果存在环，求出环上节点的个数；
如果存在环，求出链表的长度；

单链表是否有环

思路

对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后，二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。证明可以看下图：

代码

func IsRing(list *Node) bool {
	if list == nil {
		return false
	}

	p1 := list.next
	p2 := list.next
	if p2 == nil {
		return nil
	}
	p2 = p2.next
	for p1 != nil || p2 != nil {
		if p1 == p2 {
			return true
		}
		p1 = p1.next
		p2 = p2.next
		if p2 == nil {
			return false
		}
		p2 = p2.next
	}

	return false
}

找环的入口

数学证明：从链表起点head开始到入口点的距离a,与从slow和fast的相遇点到入口点的距离相等。（可以自己证明）

代码

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

	p1 := list.next
	p2 := list.next
	if p2 == nil {
		return nil
	}
	p2 = p2.next
	var meetNode *Node
	for p1 != nil || p2 != nil {
		if p1 == p2 {
			meetNode = p1
			break
		}
		p1 = p1.next
		p2 = p2.next
		if p2 == nil {
			return nil
		}
		p2 = p2.next
	}

	if meetNode == nil {
		return nil
	}

	// 再分别从头和meetNode开始走，如果相遇则是入口点
	p1 = list
	p2 = meetNode
	for p1 != p2 {
		p1 = p1.next
		p2 = p2.next
	}

	return p1
}

统计环的长度

思路

找到环的入口，再遍历一遍环则可统计环的长度

代码

func MeetNode(list *Node) int {
	if list == nil {
		return 0
	}

	p1 := list.next
	p2 := list.next
	if p2 == nil {
		return 0
	}
	p2 = p2.next
	var meetNode *Node
	for p1 != nil || p2 != nil {
		if p1 == p2 {
			meetNode = p1
			break
		}
		p1 = p1.next
		p2 = p2.next
		if p2 == nil {
			return 0
		}
		p2 = p2.next
	}

	if meetNode == nil {
		return 0
	}

	// 再分别从头和meetNode开始走，如果相遇则是入口点
	p1 = list
	p2 = meetNode
	for p1 != p2 {
		p1 = p1.next
		p2 = p2.next
	}

	// 再遍历一次环
	p := p1.next
	count := 1
	for p != p1 {
		p = p.next
		count++
	}

	return count
}

求链表长度

思路

找到环入口和已知环长度，则链表长度=环外长度+环长度

代码

func MeetNode(list *Node) int {
	if list == nil {
		return 0
	}

	p1 := list.next
	p2 := list.next
	if p2 == nil {
		return 0
	}
	p2 = p2.next
	var meetNode *Node
	for p1 != nil || p2 != nil {
		if p1 == p2 {
			meetNode = p1
			break
		}
		p1 = p1.next
		p2 = p2.next
		if p2 == nil {
			return 0
		}
		p2 = p2.next
	}

	if meetNode == nil {
		return 0
	}

	// 再分别从头和meetNode开始走，如果相遇则是入口点
	p1 = list
	p2 = meetNode
	for p1 != p2 {
		p1 = p1.next
		p2 = p2.next
	}

	// 再遍历一次环
	p := p1.next
	count := 1
	for p != p1 {
		p = p.next
		count++
	}

	// 求头到环入口p1长度
	p = list
	count1 := 0
	for p != p1 {
		count1++
		p = p.next
	}

	return count + count1
}