题解 | #链表中环的入口结点#

一.环内一定相遇: （1）fast在slow后面一步,下一次走相遇 （2）fast在slow后面两步,下一次就是（1）情况 . . . （n）fast在slow后面n步,下一次就是（n-1)情况 因此总会相遇 二.第一次相遇slow一定没走完一圈,fast没走完两圈(相遇处多走一圈) 如果slow走完一圈,则fast走两圈，fast没有追上slow,那么fast就永远不会追上 slow，与环内相遇矛盾,所以slow还在第一圈 三.在入环口处相遇 设从起点到相遇处slow走了L+a(L为起点到入口步长，a为入口到相遇处步长),fast走了2(L+a),fast比slow多走L+a,这都是在环内走的,所以环长L+a 从而,slow回到入口点要走L步，这正是起点到入口步长,让fast回到起点,二者一定在入环口相遇

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) { } }; / class Solution { public: ListNode EntryNodeOfLoop(ListNode pHead) { if(!pHead) return nullptr; ListNode* fast=pHead; ListNode* slow=pHead; while(fast && fast->next){ fast=fast->next->next; slow=slow->next; if(fast==slow) break;//第一次相遇 } if(!fast || !fast->next) return nullptr; //无环 fast=pHead; while(fast!=slow){ fast=fast->next; slow=slow->next; }//再次相遇就是入口 return fast; } };