題目

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 從鏈表的頭節(jié)點(diǎn)開始沿著 next 指針進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)為環(huán)的入口節(jié)點(diǎn)。如果鏈表無環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意，pos 僅僅是用于標(biāo)識(shí)環(huán)的情況，并不會(huì)作為參數(shù)傳遞到函數(shù)中。

• 示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

• 示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

題解

• 思路，快慢指針，如果快指針追上慢指針，證明有環(huán)
• 數(shù)學(xué)推導(dǎo)
  首先，如果有環(huán)，快指針一定能追上慢指針，假設(shè)：
  （1）從頭節(jié)點(diǎn)到入換點(diǎn)距離為a；
  （2）從入環(huán)點(diǎn)到相遇點(diǎn)距離為b；
  （3）相遇點(diǎn)到頭節(jié)點(diǎn)距離為c；
  

設(shè)快指針追上慢指針時(shí)已走了n圈，則有等式
a + (b+c)n + b = 2(a+b);==>a + (n+1)b + nc = 2(a+b); ==> a = c + (n-1)(b+c);

• 由上面等式可知，c的距離等于a的距離

ListNode *detectCycle(ListNode *head) {//快慢指針 + 數(shù)學(xué)推理bool cycle_exist = false;ListNode* slow = head, *fast = head, *tmp = head;while(fast != nullptr){if(cycle_exist){// 快指針追上慢指針后，慢指針到入環(huán)點(diǎn)的距離 與 頭節(jié)點(diǎn)到入環(huán)點(diǎn)距離相等if(slow == tmp)return slow;slow = slow->next;tmp = tmp->next;continue;}// 快指針追上慢指針，證明有環(huán)if(fast->next) fast = fast->next->next;else break;slow = slow->next;if(slow == fast) cycle_exist = true;}return nullptr;}

總結(jié)

以上是生活随笔為你收集整理的剑指 Offer II 022. 链表中环的入口节点(力扣剑指Offer专项突击版——链表2)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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