题解 | #链表中环的入口结点#
链表中环的入口结点
http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
fast := pHead
slow := pHead
// 1、先用快慢指针判断链表是否有环,如果有环找到快慢指针相遇的节点,注意该节点不一定是环的入口节点
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
break
}
}
// 2、找到快慢指针相遇的节点后,从相遇节点到入口节点的距离 == 从头节点到入口节点的距离
// 注意排除链表中只有一个节点的特例
for fast != nil && pHead != nil && pHead.Next != nil {
if fast == pHead {
return fast
}
fast = fast.Next
pHead = pHead.Next
}
return nil
}