題目描述

給一個鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結(jié)點，否則，輸出null。

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} }; */ class Solution { public:ListNode* EntryNodeOfLoop(ListNode* pHead){} };

鏈表中有環(huán)的解釋：參考：http://blog.sina.com.cn/s/blog_a1ce3d4b0102wks6.html

上圖中的第二個示例圖P2改為P1。

環(huán)中結(jié)點的數(shù)目

1）判斷一個鏈表里是否有環(huán)時用到了一快一慢兩個指針，如果兩個指針相遇，表明鏈表中存在環(huán)。兩個指針相遇的結(jié)點一定在環(huán)中，2）從這個結(jié)點出發(fā)，一邊繼續(xù)向前移動一位一遍計數(shù)，當再次回到這個結(jié)點時，就可以得到環(huán)中的節(jié)點數(shù)。

解法1：

class Solution {//找到一快一滿指針相遇處的節(jié)點，相遇的節(jié)點一定是在環(huán)中public:static ListNode* meetingNode(ListNode* head) {if(head==NULL)return NULL;ListNode* slow = head->next;if(slow==NULL)return NULL;ListNode* fast = slow->next;while (slow != NULL && fast != NULL) {if(slow==fast){return fast;}slow=slow->next;fast=fast->next;if(fast!=slow){fast=fast->next;}}return NULL;}public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* meetingNode1=meetingNode(pHead);if(meetingNode1==NULL)return NULL; // 得到環(huán)中的節(jié)點個數(shù)int nodesInLoop=1;ListNode* p1=meetingNode1;while(p1->next!=meetingNode1){p1=p1->next;++nodesInLoop;} // 移動p1p1=pHead;for(int i=0;i<nodesInLoop;i++){p1=p1->next;} // 移動p1，p2ListNode* p2=pHead;while(p1!=p2){p1=p1->next;p2=p2->next;}return p1;} };

解法2：?出錯！

class Solution { public:ListNode* EntryNodeOfLoop(ListNode* pHead){if(pHead==nullptr||pHead->next==nullptr)return nullptr;ListNode* pSlow=pHead;ListNode* pFast=pHead;while(pFast!=nullptr&&pFast->next!=nullptr){pSlow=pSlow->next;//慢結(jié)點走1步pFast=pFast->next->next;//快結(jié)點走2步if(pFast==pSlow)return pFast;}return nullptr;} }; // 故上述的這種情況只滿足：環(huán)中有結(jié)點個數(shù)為2的情況

測試結(jié)果：

您提交的程序沒有通過所有的測試用例
case通過率為50.00%

原因是事前不知道環(huán)結(jié)點有幾個，就pFast走到了第二個指針。

解法:3：其它的思路
//先說個定理：兩個指針一個fast、一個slow同時從一個鏈表的頭部出發(fā)
//fast一次走2步，slow一次走一步，如果該鏈表有環(huán)，兩個指針必然在環(huán)內(nèi)相遇
//此時只需要把其中的一個指針重新指向鏈表頭部，另一個不變（還在環(huán)內(nèi)），
//這次兩個指針一次走一步，相遇的地方就是入口節(jié)點。
//https://blog.csdn.net/snow_7/article/details/52181049
https://blog.csdn.net/WitsMakeMen/article/details/37597291

class Solution {public:ListNode* EntryNodeOfLoop(ListNode* pHead){if(pHead==nullptr|| pHead->next==nullptr|| pHead->next->next==nullptr)return nullptr;ListNode* fast=pHead->next->next;ListNode* slow=pHead->next;//先判斷有沒有環(huán)while(fast!=slow){if(fast->next!=nullptr&& fast->next->next!=nullptr){fast=fast->next->next;slow=slow->next;}else{//沒有環(huán),返回return nullptr;}}//跳出上述循環(huán)，則有環(huán)，此時fast=slow.fast=pHead;//重新定義fast結(jié)點的位置為頭結(jié)點while(fast!=slow){fast=fast->next;slow=slow->next;}return slow;} };

通過！

但是沒有像之前說的要找出結(jié)點的個數(shù)！

類似解法：

//左神講的 //先說個定理：兩個指針一個fast、一個slow同時從一個鏈表的頭部出發(fā) //fast一次走2步，slow一次走一步，如果該鏈表有環(huán)，兩個指針必然在環(huán)內(nèi)相遇 //此時只需要把其中的一個指針重新指向鏈表頭部，另一個不變（還在環(huán)內(nèi)）， //這次兩個指針一次走一步，相遇的地方就是入口節(jié)點。 //這個定理可以自己去網(wǎng)上看看證明。https://blog.csdn.net/snow_7/article/details/52181049 //https://www.cnblogs.com/snake-hand/p/3148328.html class Solution {public: ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode* fast = pHead;ListNode* slow = pHead;while(fast != NULL && fast->next !=NULL){fast = fast->next->next;slow = slow->next;if(fast == slow)break;}if(fast == NULL || fast->next == NULL)return NULL;fast=pHead;while(fast!=slow){fast=fast->next;slow=slow->next;}return fast;} };

?

參考：

【1】https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

【2】思路2的定理?https://blog.csdn.net/WitsMakeMen/article/details/37597291?待續(xù)

總結(jié)

以上是生活随笔為你收集整理的8.找出链表环的入口结点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。