一、題目描述

給定一個(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)，評測系統(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, 10^4]?內(nèi)
• -10^5 <= Node.val <= 10^5
• pos?的值為?-1?或者鏈表中的一個(gè)有效索引

二、解題思路

這個(gè)問題是著名的“鏈表環(huán)入口”問題，可以使用“快慢指針”的解法來解決。以下是詳細(xì)的解題步驟：

1. 初始化兩個(gè)指針，一個(gè)快指針（fast）和一個(gè)慢指針（slow），它們都從鏈表的頭節(jié)點(diǎn)開始移動(dòng)。

2. 移動(dòng)快慢指針，快指針每次移動(dòng)兩步，慢指針每次移動(dòng)一步。

3. 檢查是否有環(huán)，如果快指針和慢指針相遇，則說明鏈表存在環(huán)。

4. 尋找環(huán)的入口，當(dāng)快慢指針相遇后，將其中一個(gè)指針（例如慢指針）移動(dòng)到鏈表的頭節(jié)點(diǎn)，另一個(gè)指針保持在相遇點(diǎn)。然后，兩個(gè)指針以相同的速度移動(dòng)，當(dāng)它們再次相遇時(shí)，所在的位置就是環(huán)的入口。

5. 返回結(jié)果，如果鏈表無環(huán)，則返回 null；如果有環(huán)，則返回環(huán)的入口節(jié)點(diǎn)。

三、具體代碼

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;boolean hasCycle = false;// 檢查是否有環(huán)while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {hasCycle = true;break;}}// 如果沒有環(huán)，返回 nullif (!hasCycle) {return null;}// 尋找環(huán)的入口slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow; // 返回環(huán)的入口節(jié)點(diǎn)}
}

四、時(shí)間復(fù)雜度和空間復(fù)雜度

1. 時(shí)間復(fù)雜度

• 檢查是否有環(huán)的階段：

  • 初始化兩個(gè)指針，一個(gè)快指針（每次移動(dòng)兩步）和一個(gè)慢指針（每次移動(dòng)一步）。
  • 假設(shè)鏈表總長度為 L，非環(huán)部分長度為 a，環(huán)部分長度為 b。
  • 在沒有遇到環(huán)的情況下，快指針和慢指針最多移動(dòng) L 步，即 L = a + b。
  • 當(dāng)快慢指針都進(jìn)入環(huán)中后，它們會(huì)在環(huán)中相遇。設(shè)它們在環(huán)中相遇前，快指針比慢指針多走了 n 步，則有 n = b。
  • 快慢指針相遇時(shí)，它們分別走了 a + b 和 a + b - n 步，即快指針走了 L 步，慢指針走了 L - n 步。
  • 由于快指針走的步數(shù)是慢指針的兩倍，所以有 2(L - n) = L，解得 n = L/2。
  • 因此，慢指針在環(huán)中走了 L/2 步，快指針走了 L 步，它們相遇的時(shí)間復(fù)雜度為 O(L)。

• 尋找環(huán)的入口的階段：

  • 將慢指針移回鏈表頭部，快指針保持在相遇點(diǎn)。
  • 由于慢指針在環(huán)中已經(jīng)走了 L/2 步，且快指針在相遇點(diǎn)，所以它們相遇時(shí)，慢指針走了 a 步，快指針走了 a + b 步。
  • 因此，它們相遇的時(shí)間復(fù)雜度為 O(a)。

綜上所述，總的時(shí)間復(fù)雜度為 O(L)。

2. 空間復(fù)雜度

• 該算法只使用了幾個(gè)指針變量，沒有使用額外的數(shù)據(jù)結(jié)構(gòu)。
• 因此，空間復(fù)雜度為 O(1)。

五、總結(jié)知識(shí)點(diǎn)

1. 鏈表操作：代碼中涉及到鏈表的基本操作，包括遍歷鏈表、判斷節(jié)點(diǎn)是否為空、移動(dòng)指針等。

2. 快慢指針技巧：這是解決鏈表相關(guān)問題的一種常用技巧，通過設(shè)置兩個(gè)指針，一個(gè)快一個(gè)慢，來解決問題。在本題中，快指針每次移動(dòng)兩步，慢指針每次移動(dòng)一步，用于檢測鏈表中是否存在環(huán)。

3. 循環(huán)檢測：通過快慢指針的相遇來判斷鏈表中是否存在環(huán)。如果快慢指針相遇，則說明鏈表中有環(huán)；如果快指針遇到空節(jié)點(diǎn)，則說明鏈表中無環(huán)。

4. 數(shù)學(xué)推理：當(dāng)快慢指針在環(huán)中相遇時(shí)，通過數(shù)學(xué)推理可以得出慢指針走過的距離和環(huán)的入口之間的關(guān)系，從而找到環(huán)的入口。

5. 邊界條件處理：代碼中需要處理鏈表為空或者鏈表沒有環(huán)的情況，這需要仔細(xì)考慮邊界條件，確保代碼的魯棒性。

以上就是解決這個(gè)問題的詳細(xì)步驟，希望能夠?yàn)楦魑惶峁﹩l(fā)和幫助。