給定一個(gè)鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(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)。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒(méi)有環(huán)。

這道題目，不僅考察對(duì)鏈表的操作，而且還需要一些數(shù)學(xué)運(yùn)算。

主要考察兩知識(shí)點(diǎn)：

• 判斷鏈表是否環(huán)

• 如果有環(huán)，如何找到這個(gè)環(huán)的入口

判斷鏈表是否有環(huán)

可以使用快慢指針?lè)?#xff0c;分別定義 fast 和 slow 指針，從頭結(jié)點(diǎn)出發(fā)，fast指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)，slow指針每次移動(dòng)一個(gè)節(jié)點(diǎn)，如果 fast 和 slow指針在途中相遇 ，說(shuō)明這個(gè)鏈表有環(huán)。

為什么fast 走兩個(gè)節(jié)點(diǎn)，slow走一個(gè)節(jié)點(diǎn)，有環(huán)的話，一定會(huì)在環(huán)內(nèi)相遇呢，而不是永遠(yuǎn)的錯(cuò)開呢

首先第一點(diǎn)：fast指針一定先進(jìn)入環(huán)中，如果fast指針和slow指針相遇的話，一定是在環(huán)中相遇，這是毋庸置疑的。

那么來(lái)看一下，為什么fast指針和slow指針一定會(huì)相遇呢？

可以畫一個(gè)環(huán)，然后讓 fast指針在任意一個(gè)節(jié)點(diǎn)開始追趕slow指針。

會(huì)發(fā)現(xiàn)最終都是這種情況， 如下圖：

fast和slow各自再走一步， fast和slow就相遇了

這是因?yàn)閒ast是走兩步，slow是走一步，其實(shí)相對(duì)于slow來(lái)說(shuō)，fast是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的靠近slow的，所以fast一定可以和slow重合。

如果有環(huán)，如何找到這個(gè)環(huán)的入口

此時(shí)已經(jīng)可以判斷鏈表是否有環(huán)了，那么接下來(lái)要找這個(gè)環(huán)的入口了。

假設(shè)從頭結(jié)點(diǎn)到環(huán)形入口節(jié)點(diǎn) 的節(jié)點(diǎn)數(shù)為x。 環(huán)形入口節(jié)點(diǎn)到 fast指針與slow指針相遇節(jié)點(diǎn) 節(jié)點(diǎn)數(shù)為y。 從相遇節(jié)點(diǎn) 再到環(huán)形入口節(jié)點(diǎn)節(jié)點(diǎn)數(shù)為 z。?

那么相遇時(shí)： slow指針走過(guò)的節(jié)點(diǎn)數(shù)為: x + y， fast指針走過(guò)的節(jié)點(diǎn)數(shù)：x + y + n (y + z)，n為fast指針在環(huán)內(nèi)走了n圈才遇到slow指針， （y+z）為 一圈內(nèi)節(jié)點(diǎn)的個(gè)數(shù)A。

因?yàn)閒ast指針是一步走兩個(gè)節(jié)點(diǎn)，slow指針一步走一個(gè)節(jié)點(diǎn)， 所以 fast指針走過(guò)的節(jié)點(diǎn)數(shù) = slow指針走過(guò)的節(jié)點(diǎn)數(shù) * 2：

(x + y) * 2 = x + y + n (y + z)

兩邊消掉一個(gè)（x+y）: x + y = n (y + z)

因?yàn)橐噎h(huán)形的入口，那么要求的是x，因?yàn)閤表示 頭結(jié)點(diǎn)到 環(huán)形入口節(jié)點(diǎn)的的距離。

所以要求x ，將x單獨(dú)放在左面：x = n (y + z) - y ,

再?gòu)膎(y+z)中提出一個(gè) （y+z）來(lái)，整理公式之后為如下公式：x = (n - 1) (y + z) + z 注意這里n一定是大于等于1的，因?yàn)?fast指針至少要多走一圈才能相遇slow指針。

這個(gè)公式說(shuō)明什么呢？

先拿n為1的情況來(lái)舉例，意味著fast指針在環(huán)形里轉(zhuǎn)了一圈之后，就遇到了 slow指針了。

當(dāng) n為1的時(shí)候，公式就化解為 x = z，

這就意味著，從頭結(jié)點(diǎn)出發(fā)一個(gè)指針，從相遇節(jié)點(diǎn) 也出發(fā)一個(gè)指針，這兩個(gè)指針每次只走一個(gè)節(jié)點(diǎn)， 那么當(dāng)這兩個(gè)指針相遇的時(shí)候就是 環(huán)形入口的節(jié)點(diǎn)。

也就是在相遇節(jié)點(diǎn)處，定義一個(gè)指針index1，在頭結(jié)點(diǎn)處定一個(gè)指針index2。

讓index1和index2同時(shí)移動(dòng)，每次移動(dòng)一個(gè)節(jié)點(diǎn)， 那么他們相遇的地方就是 環(huán)形入口的節(jié)點(diǎn)。

那么 n如果大于1是什么情況呢，就是fast指針在環(huán)形轉(zhuǎn)n圈之后才遇到 slow指針。

其實(shí)這種情況和n為1的時(shí)候 效果是一樣的，一樣可以通過(guò)這個(gè)方法找到 環(huán)形的入口節(jié)點(diǎn)，只不過(guò)，index1 指針在環(huán)里 多轉(zhuǎn)了(n-1)圈，然后再遇到index2，相遇點(diǎn)依然是環(huán)形的入口節(jié)點(diǎn)。

解：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有環(huán)ListNode index1 = fast;ListNode index2 = head;// 兩個(gè)指針，從頭結(jié)點(diǎn)和相遇結(jié)點(diǎn)，各走一步，直到相遇，相遇點(diǎn)即為環(huán)入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}