当fast指针等于slow指针时，slow指针肯定还没有遍历完整个链表，而此时fast指针已经在环内循环了n圈(n>=1)，假定从链表头指针开始slow走了s步，则fast走了2s步，fast所走的步数还等于s加上fast指针比slow指针在环内多走的n圈。设环长为r，则：
2s = s + nr;
=>s = nr;
设整个链表长度为L，环的入口结点到相遇结点的距离为x, 起点到环的入口结点的距离为a.
a + x = nr;
=> a + x = (n-1)r + L - a;
=> a = (n-1)r + (L - a - x);
=> 由链表的头结点到环入口结点的距离等于n-1圈环的长度+相遇点到环入口结点的距离，于是，当我们在链表头部和相遇处分别设一指针，每次各走一步，则两指针必定相遇，且相遇的第一个结点即为环的入口结点
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead==NULL||pHead->next==NULL) return NULL; ListNode* pfast=pHead; ListNode* pslow=pHead; while(pfast&&pfast->next) { pfast=pfast->next->next; pslow=pslow->next; if(pfast==pslow) break; } pfast=pHead; while(pfast!=pslow) { pfast=pfast->next; pslow=pslow->next; } return pfast; } }; //第二种方法：使用set库函数（哈希表）存储，将当前节点与set中存储的结点比较，找出第一个重复的结点，即为入口 /* class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead==NULL || pHead->next==NULL) return NULL; set<ListNode*> listSet; while(pHead!=NULL){ if(listSet.find(pHead)==listSet.end()){ listSet.insert(pHead); pHead=pHead->next; } else return pHead; } return NULL; } }; */ 还有一种方法破坏链表结构，但是也能通过测试算例/* 时间复杂度为O（n），两个指针，一个在前面，另一个紧邻着这个指针，在后面。 两个指针同时向前移动，每移动一次，前面的指针的next指向NULL。 也就是说：访问过的节点都断开，最后到达的那个节点一定是尾节点的下一个， 也就是循环的第一个。 这时候已经是第二次访问循环的第一节点了，第一次访问的时候我们已经让它指向了NULL， 所以到这结束。 */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if (!pHead->next) return NULL; ListNode* previous = pHead; ListNode* front = pHead ->next; while (front) { previous->next = NULL; previous = front; front = front->next; } return previous; } };
同 LeetCode--linked-list-cycle-ii
