这题要找出链表中环的入口，如果链表中没有环，则返回空。前面我们讲过《判断链表是否有环》，所以我们可以根据前面的解来判断链表是否有环，如果没环，自然就不可能有环的入口。如果有环我们再来找出环的入口，怎么找呢？如下图所示。
在相遇点快指针走过的距离是： a+c+(b+c)*m，其中 b+c 是环的周长， m 是快指针在环上转了 m 圈之后和慢指针相遇。慢指针走过的距离是： a+c+(b+c)*n，其中 n 是慢指针在环上转了 n 圈之后和快指针相遇，很明显 n < m 。
由于快指针每次走两步，慢指针每次走一步，所以快指针走的距离是慢指针的 2 倍，也就是：
a+c+(b+c)*m = 2*(a+c+(b+c)*n)
整理之后可以得到：a+c= (b+c)*(m-2*n)，也就是说 a+c 的长度等于 (m-2*n) 个环的长度。在整理一下又可以变成：
a = (b+c)*(m-2*n-1)+b。其中 (b+c)*(m-2*n-1) 是在环上走了整整 (m-2*n-1) 圈。
这个时候如果我们使用两个指针，一个从起始位置开始，一个从相遇点开始，每次都走一步，最终它们一定会在环的入口相遇。
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = pHead;// 快指针
ListNode fast = pHead;// 慢指针
while (fast != null && fast.next != null) {
// 快慢指针，快指针每次走两步，慢指针每次走一步
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {// 如果相遇，说明有环
// 确定有环之后才能找环的入口
while (pHead != slow) {
// 两指针，一个从头结点开始，一个从相遇点
// 开始每次走一步，直到再次相遇为止
pHead = pHead.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
public:
ListNode *EntryNodeOfLoop(ListNode *pHead) {
ListNode *slow = pHead;// 快指针
ListNode *fast = pHead;// 慢指针
while (fast && fast->next) {
// 快慢指针，快指针每次走两步，慢指针每次走一步
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {// 先判断是否有环，
// 确定有环之后才能找环的入口
while (pHead != slow) {
// 两指针，一个从头结点开始，一个从相遇点
// 开始每次走一步，直到再次相遇为止
pHead = pHead->next;
slow = slow->next;
}
return slow;
}
}
return nullptr;
}
京公网安备 11010502036488号