[剑指offer] 55. 链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出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;}
};