题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路:
用两个指针代表一快一慢的指针，快指针一次前进2个单位，慢指针一次前进1个单位。两个指针同时出发。
若存在环，设环中有n个节点且当下一次两个指针相遇时：
慢指针前进了X个单位，快指针前进了2X个单位。
则有 2X=n+X 推导出 n = X。则慢指针走了一个环的步数，快指针走了两个环的步数。
此时让快指针指向头指针，两个指针都按一次1个单位前进，直到下一次相遇时，此时两个指针指向环的起点。
class Solution
{
public:
ListNode *EntryNodeOfLoop(ListNode *
pHead)
{
if (pHead == NULL || pHead->next ==
NULL)
return NULL;
ListNode *p1 =
pHead;
ListNode *p2 =
pHead;
while (p1 != NULL && p2 !=
NULL)
{
p1 = p1->
next;
p2 = p2->next->
next;
if (p1 ==
p2)
{
p2 =
pHead;
while (p1 !=
p2)
{
p1 = p1->
next;
p2 = p2->
next;
}
if (p1 ==
p2)
return p1;
}
}
return NULL;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10239316.html
