題目描述

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

題目分析

鏈表中某些結(jié)點構(gòu)成了一個環(huán)，找打環(huán)的入口結(jié)點

思路：

? head->a1->a2->a3...

使用雙層循環(huán)，例如對于結(jié)點a1，遍歷整個鏈表判斷是否有a1 = head->next；(head = head->next);a2,a3,......an;依次

測試報錯，沒通過

/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/class Solution { public:ListNode* EntryNodeOfLoop(ListNode* pHead){//找到某個結(jié)點地址與鏈表中默認(rèn)結(jié)點的next指針域的地址相同，即為鏈表中的環(huán)//定義一個ListNode* temp = pHead;//定義一個遍歷結(jié)點pListNode* p = temp；//循環(huán)條件：遍歷結(jié)點非空;需要使用雙層循環(huán)，類似“冒泡”找出鏈表中的環(huán)while(temp){while(p){p = p->next;if（temp != p）{p = p->next;}else{return temp;break;}}temp = temp->next;}if(temp == NULL){return null;}} };

另外，參考：卻顧所來徑

step1、找兩者相遇點

設(shè)置兩個指針，快指針fast每次走兩個結(jié)點的距離，慢指針slow每次走一個結(jié)點的距離；

鏈表中沒有環(huán)，直到走完整個鏈表，slow不可能追上fast；

鏈表中有環(huán)，fast先進(jìn)環(huán)，繞環(huán)走，slow后進(jìn)環(huán)，相相當(dāng)于fast在追slow，兩者一定會相遇；

step2:

兩個指針，slow從表頭開始走，fast從相遇點開始走（兩者速度一樣，每次走一個結(jié)點），最后一定相遇與環(huán)入口；

表頭到環(huán)入口的距離為A；環(huán)入口到相遇點的距離為B；相遇點到環(huán)入口距離為C；

實現(xiàn)過程：

1、當(dāng)fast、slow兩者相遇時，快指針的路程是慢指針路程的兩倍：

（因為兩者走是同步的，只不過fast速度是slow的兩倍，不管相不相遇，同一時刻，fast走的路程都是slow的兩倍）

fast走的路程：A+（B+C）*K+B

slow走的路程：A+B

（A+B）*2 =?A+（B+C）*K+B? --》 A = （K-1）*（B+C）+C? ? ? ? ?（1）?

?即，鏈表頭到環(huán)入口的距離 = 相遇點到環(huán)入口距離 + 環(huán)長度*（K-1）

2、記錄相遇結(jié)點之后，讓fast從相遇結(jié)點開始走，slow從表頭開始走，兩者一定在環(huán)入口相遇。

為什么會在環(huán)入口相遇？根據(jù)公式（1）計算得到

class Solution { public:ListNode* EntryNodeOfLoop(ListNode* pHead){//先找fast與slow相遇點ListNode* fast = pHead;ListNode* slow = pHead;if（pHead == nullptr || pHead->next == nullptr）{return nullptr;}while(fast && slow){fast = fast->next->next;slow = slow->next;if(fast == slow){break;}else{return nullptr；}}//fast從相遇點出發(fā)，slow從表頭出發(fā)slow = pHead;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;} };

測試通過代碼

class Solution{ public:ListNode *EntryNodeOfLoop(ListNode* pHead){ListNode* fast = pHead;//fast從表頭出發(fā) ListNode* slow = pHead;//slow從表頭出發(fā) while(fast && fast->next){ // 表頭及表頭下一個結(jié)點不為null //fast每次走兩個結(jié)點的距離 fast = fast->next->next;//slow每次走一個結(jié)點的距離 slow = slow->next;//當(dāng)fast == slow說明兩個指針在環(huán)中相遇 if(fast == slow){break;}} //此時fast 及fast->next為空，返回null if(!fast || !fast->next)return NULL; // 難點：slow從表頭出發(fā)，fast從相遇點出發(fā)，為什么當(dāng)fast和slow相遇一定是在環(huán)入口 // 本身數(shù)據(jù)結(jié)構(gòu)不難，難的是，將問題抽象為數(shù)學(xué)模型 slow = pHead;//low從鏈表頭出發(fā)while(fast != slow){//fast 從相遇點出發(fā)fast = fast->next;slow = slow->next; } return slow;} };

?

總結(jié)

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

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