142-環形連結清單 II
- 題目描述
- 我的解題思路(Floyd判圈)(快慢指針)
-
- 代碼
- 時間複雜度&空間複雜度
題目描述
給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。
為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意，
pos
僅僅是用于辨別環的情況，并不會作為參數傳遞到函數中。
說明：不允許修改給定的連結清單。
進階：
- 你是否可以使用 O(1) 空間解決此題？
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：傳回索引為 1 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：傳回索引為 0 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1
輸出：傳回 null
解釋：連結清單中沒有環。
提示：
- 連結清單中節點的數目範圍在範圍 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值為 -1 或者連結清單中的一個有效索引
我的解題思路(Floyd判圈)(快慢指針)
在做過leetcode-尋找重複數這題之後已經回想起了Floyd判圈的結論,然後解決環形連結清單的入口問題就非常簡單了
結論:
- 一個快指針fast,一個慢指針slow都指向頭結點，fast一次走兩步，slow一次走一步，如果連結清單存在環，那麼必然fast和slow會有一個重合點。
- 一個指針before指向頭結點,一個指針after指向重合點，速度相同，然後走到的新的重合點就是環形連結清單的入口。
代碼
//detect: 探測
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
//慢指針
ListNode slow = head;
//快指針
ListNode fast = head;
// 這邊要先走一次，再判斷，不然剛開始就滿足條件，就出bug了，找了半天
do {
fast = fast.next.next;
slow = slow.next;
} while (fast != null && fast.next != null && fast != slow);
if (fast == null || fast.next == null) {
return null;
}
//指向頭結點
ListNode before = head;
//指向重合的結點
ListNode after = fast;
while (before != after) {
before = before.next;
after = after.next;
}
return before;
}
時間複雜度&空間複雜度
時間複雜度: O(N)
空間複雜度: O(1)