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

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) { } }; / class Solution { public: ListNode EntryNodeOfLoop(ListNode pHead) { //判断链表是否有环的一种典中典的做法是快慢指针算法 //这个算法如果以前没用过或者没见过不是人脑子能想出来的， //这题就当给大家分享一下这个方法自己也熟悉一下，顺便练下coding吧 //何为快慢指针呢？即快指针一次走两步慢指针一次走一步，很简单吧 ListNode* fastP=pHead,*lowP=pHead; if(fastP==NULL||fastP->next==NULL)//即若走一个节点就到头了或者压根就没节点，则肯定无环 return NULL; else{//否则，先让快指针走两步，慢指针走一步 fastP=fastP->next->next; lowP=lowP->next; } while(fastP&&fastP->next&&fastP!=lowP)//当快指针不为空，且快指针的下一个不空且快指针不等于慢指针时继续 { fastP=fastP->next->next; lowP=lowP->next; } if(fastP==NULL||fastP->next==NULL) return NULL; else{//如果不是因为快指针走到空循环结束，那么说明一定是快慢指针相遇了 //快慢指针相遇后让快指针回到头结点，慢指针不动，然后快慢指针每次都只走一步，最后再次相遇的节点就是入环口 //是不是无法接受，但是就是这么魔幻，数学证明感兴趣自行百度 fastP=pHead; while(fastP!=lowP) { fastP=fastP->next; lowP=lowP->next; } return fastP; } } };