給定一個鏈表，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。

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

?

示例 1：

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

示例?2：

輸入：head = [1,2], pos = 0 輸出：tail connects to node index 0 解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1 輸出：no cycle 解釋：鏈表中沒有環。

?

進階：
你是否可以不用額外空間解決此題？

快慢指針

跟昨天那題差不多，昨天用了哈希表，今天就用個快慢指針吧。

我們使用兩個指針，$\text{fast}$ 與 $\text{slow}$。它們起始都位于鏈表的頭部。隨后，$\text{slow}$ 指針每次向后移動一個位置，而 $\text{fast}$ 指針向后移動兩個位置。如果鏈表中存在環，則 $\text{fast}$ 指針最終將再次與 $\text{slow}$ 指針在環中相遇。

如下圖所示，設鏈表中環外部分的長度為 $a$。$\text{slow}$ 指針進入環后，又走了 $b$ 的距離與 $\text{fast}$ 相遇。此時，$\text{fast}$ 指針已經走完了環的 $n$ 圈，因此它走過的總距離為 $a+n(b+c)+b=a+(n+1)b+nc$。

根據題意，任意時刻，$\text{fast}$ 指針走過的距離都為 $\text{slow}$ 指針的 $2$ 倍。因此，我們有

$$a+(n+1)b+nc=2(a+b)?a=c+(n?1)(b+c)$$

有了 $a=c+(n?1)(b+c)$ 的等量關系，我們會發現：從相遇點到入環點的距離加上 $n?1$ 圈的環長，恰好等于從鏈表頭部到入環點的距離。

因此，當發現 $\text{slow}$ 與 $\text{fast}$ 相遇時，我們再額外使用一個指針 $\text{ptr}$。起始，它指向鏈表頭部；隨后，它和 $\text{slow}$ 每次向后移動一個位置。最終，它們會在入環點相遇。

總結

以上是生活随笔為你收集整理的142. Linked List Cycle II 环形链表 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。