題目：

??給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

??說明：不允許修改給定的鏈表。

示例 1：
??輸入：head = [3,2,0,-4], pos = 1
??輸出：tail connects to node index 1
??解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：
??輸入：head = [1,2], pos = 0
??輸出：tail connects to node index 0
??解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：
??輸入：head = [1], pos = -1
??輸出：no cycle
??解釋：鏈表中沒有環(huán)。

解題思路：

??看到這道題分兩步去做，我們首先要考慮的是這個鏈表有沒有帶環(huán)，如果沒有帶環(huán)，直接返回NULL就可以，如果帶環(huán)了，就開始去找入口點：
??1、使用快慢指針來判斷鏈表是否有環(huán)：
??如果這個鏈表沒有尾節(jié)點（pCur == NULL），那么這個節(jié)點就是帶環(huán)的，要怎么來判斷呢？如果是while(pCur)這樣肯定不行，如果這個鏈表帶環(huán)，就成了死循環(huán)，所以要使用一對快慢指針來判斷是否帶環(huán)，讓快指針一次由兩步，慢指針一次走一步，如果這個鏈表帶環(huán)，在一定的時間內(nèi)這兩個指針一定會相遇。
??2、通過兩個指針找?guī)Лh(huán)鏈表的換入口節(jié)點：
??一個指針從快慢指針的相遇節(jié)點開始，每次走一步，零一個指針從鏈表的頭節(jié)點開始每次走一步，他們的相遇點就是入口節(jié)點，為什么這兩個指針的相遇節(jié)點就是入口節(jié)點呢？下面用途來分析

結(jié)合上圖開始推導(dǎo)：
??快指針在相遇前走的距離：L+X+nR
??慢指針在相遇前走的距離：L+X
??所以：2(L+X) = L+XnR
?????? ? L = nR-X
??n的最小值取1，那么就是L = R-X，所以當(dāng)這兩個指針走的路是一樣長，那么他們相遇的節(jié)點就是入口節(jié)點。

代碼解析：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *detectCycle(ListNode *head) {//先判斷是否有環(huán)ListNode* pFast = head;ListNode* pSlow = head;while(pFast && pFast->next){pFast = pFast->next->next;pSlow = pSlow->next;if(pFast == pSlow)break;}if(pFast == NULL || pSlow == NULL)return NULL;//找入口節(jié)點else{ListNode* pCyc = pFast;ListNode* pLine = head;while(pCyc != pLine){pCyc = pCyc->next;pLine = pLine->next;}return pCyc;}} }; 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

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