思路:
- 用快慢指针判断有没有环(fast每次走两步,slow每次一步)
- 若有,返还相遇的指针,此时指针必定相遇在环中
- 遍历环,得到环的数目n
- 一个指针先走n步,另一个指针再开始走(它们的速度相同),它们相遇的地方就是入口(相当于“链表倒数第k个结点”)
ListNode* EntryNodeOfLoop(ListNode* pHead){if(!pHead || !(pHead->next))return NULL;ListNode* fast = pHead;ListNode* slow = pHead;while(fast && fast->next && fast->next->next){fast = fast->next->next;slow = slow->next;if(fast == slow)break;}if(!fast || !(fast->next) || !(fast->next->next))return NULL;fast = fast->next;int len = 1;while(fast != slow){fast = fast->next;len++;}fast = pHead;slow = pHead;for(int i = 0;i < len;i++)fast = fast->next;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}
