上傳自己做的網(wǎng)站后臺(tái)怎么辦常見的網(wǎng)絡(luò)營銷方式有哪些
一、題目描述
給定一個(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ì)的解題步驟:
-
初始化兩個(gè)指針,一個(gè)快指針(fast)和一個(gè)慢指針(slow),它們都從鏈表的頭節(jié)點(diǎn)開始移動(dòng)。
-
移動(dòng)快慢指針,快指針每次移動(dòng)兩步,慢指針每次移動(dòng)一步。
-
檢查是否有環(huán),如果快指針和慢指針相遇,則說明鏈表存在環(huán)。
-
尋找環(huán)的入口,當(dāng)快慢指針相遇后,將其中一個(gè)指針(例如慢指針)移動(dòng)到鏈表的頭節(jié)點(diǎn),另一個(gè)指針保持在相遇點(diǎn)。然后,兩個(gè)指針以相同的速度移動(dòng),當(dāng)它們再次相遇時(shí),所在的位置就是環(huán)的入口。
-
返回結(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)
-
鏈表操作:代碼中涉及到鏈表的基本操作,包括遍歷鏈表、判斷節(jié)點(diǎn)是否為空、移動(dòng)指針等。
-
快慢指針技巧:這是解決鏈表相關(guān)問題的一種常用技巧,通過設(shè)置兩個(gè)指針,一個(gè)快一個(gè)慢,來解決問題。在本題中,快指針每次移動(dòng)兩步,慢指針每次移動(dòng)一步,用于檢測鏈表中是否存在環(huán)。
-
循環(huán)檢測:通過快慢指針的相遇來判斷鏈表中是否存在環(huán)。如果快慢指針相遇,則說明鏈表中有環(huán);如果快指針遇到空節(jié)點(diǎn),則說明鏈表中無環(huán)。
-
數(shù)學(xué)推理:當(dāng)快慢指針在環(huán)中相遇時(shí),通過數(shù)學(xué)推理可以得出慢指針走過的距離和環(huán)的入口之間的關(guān)系,從而找到環(huán)的入口。
-
邊界條件處理:代碼中需要處理鏈表為空或者鏈表沒有環(huán)的情況,這需要仔細(xì)考慮邊界條件,確保代碼的魯棒性。
以上就是解決這個(gè)問題的詳細(xì)步驟,希望能夠?yàn)楦魑惶峁﹩l(fā)和幫助。