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

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環(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
解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍?[0, 104]?內(nèi)
• -105 <= Node.val <= 105
• pos?的值為?-1?或者鏈表中的一個(gè)有效索引

進(jìn)階：你是否可以使用?O(1)?空間解決此題？

    /*** fast 走的步數(shù)是 slow 步數(shù)的 2 倍，即 f=2s* fast 比 slow 多走了 n 個(gè)環(huán)的長度，即 f=s+nb* 上兩式相減得到 f=2nb，s = nb,即 fast 和 slow 指針分別走了 2n，n 個(gè)環(huán)的周長。* @param head* @return*/public ListNode detectCycle(ListNode head) {ListNode fast = head, slow = head;while (true) {if (fast == null || fast.next == null) {return null;}fast = fast.next.next;slow = slow.next;// 制造第一次相遇if (slow == fast) break;}// 走到鏈表入口節(jié)點(diǎn)時(shí)的步數(shù) 是：k=a+nb// 此時(shí)求a的步數(shù)即可求出，環(huán)形入口的結(jié)點(diǎn)fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}// 此時(shí)就是相遇的結(jié)點(diǎn)return fast;}