摘要
連結串列問題中，查詢環的起始節點是一個經典的進階題目。本篇文章將講解如何在 Swift 中實現 查詢連結串列入環點 的演算法，並透過 快慢指標法 實現 O(1) 空間複雜度，詳細分析程式碼邏輯並給出完整的測試案例。
描述
給定一個連結串列的頭節點 head ，返回連結串列開始入環的第一個節點。 如果連結串列無環，則返回 null。
如果連結串列中有某個節點，可以透過連續跟蹤 next 指標再次到達，則連結串列中存在環。 爲了表示給定連結串列中的環，評測系統內部使用整數 pos 來表示連結串列尾連線到連結串列中的位置（索引從 0 開始）。如果 pos 是 -1，則在該連結串列中沒有環。注意：pos 不作為引數進行傳遞，僅僅是爲了標識連結串列的實際情況。
不允許修改 連結串列。
示例 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 <= 105pos的值為-1或者連結串列中的一個有效索引
進階： 你是否可以使用 O(1) 空間解決此題？
題解答案
我們採用 快慢指標法 解決該問題。
在之前判斷連結串列是否存在環的基礎上，進一步確定環的起始節點。
核心思路：
使用快慢指標判斷連結串列是否有環。
若有環，快慢指標相遇時，將其中一個指標重新指向連結串列頭節點，並保持另一個指標在相遇點。
兩個指標以相同的速度前進，相遇時的節點即為入環點。
題解程式碼
以下是 Swift 實現程式碼：
// 定義連結串列節點
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func detectCycle(_ head: ListNode?) -> ListNode? {
var slow = head
var fast = head
// 快慢指標判斷是否有環
while let nextFast = fast?.next {
slow = slow?.next
fast = nextFast.next
if slow === fast {
// 有環，查詢環的起點
var pointer1 = head
var pointer2 = slow
while pointer1 !== pointer2 {
pointer1 = pointer1?.next
pointer2 = pointer2?.next
}
return pointer1
}
}
// 無環
return nil
}
題解程式碼分析
快慢指標的初始化
慢指標每次走一步，快指標每次走兩步。
快指標達到連結串列末尾時（
fast == nil或fast.next == nil），說明連結串列無環。檢測環的存在
若快慢指標在某個節點相遇，則連結串列中存在環。
慢指標和快指標的路徑會在環中迴圈，從而必定相遇。
確定環的起始節點
相遇後，將其中一個指標（如
pointer1）重新指向連結串列頭節點，另一個指標（如pointer2）保持在相遇點。兩個指標每次走一步，最終相遇時的節點即為環的起始節點。
時間複雜度
檢測環的階段：
O(n)，連結串列節點最多被訪問兩次。找入環點的階段：
O(n)，快慢指標最多走一圈。總時間複雜度：
O(n)。空間複雜度
只使用了兩個指標，空間複雜度為
O(1)。
示例測試及結果
以下是測試程式碼：
// 建立測試用例
func createLinkedListWithCycle(_ values: [Int], _ pos: Int) -> ListNode? {
guard !values.isEmpty else { return nil }
let head = ListNode(values[0])
var current = head
var cycleNode: ListNode? = nil
for i in 1..<values.count {
let node = ListNode(values[i])
current.next = node
current = node
if i == pos {
cycleNode = node
}
}
// 建立環
if let cycleNode = cycleNode {
current.next = cycleNode
}
return head
}
// 示例 1
let head1 = createLinkedListWithCycle([3, 2, 0, -4], 1)
print(detectCycle(head1)?.val ?? "No cycle") // 輸出: 2
// 示例 2
let head2 = createLinkedListWithCycle([1, 2], 0)
print(detectCycle(head2)?.val ?? "No cycle") // 輸出: 1
// 示例 3
let head3 = createLinkedListWithCycle([1], -1)
print(detectCycle(head3)?.val ?? "No cycle") // 輸出: No cycle
測試結果:
2 1 No cycle
時間複雜度
檢測環的複雜度：每個節點最多訪問兩次，複雜度為
O(n)。找入環點的複雜度：環內最多走一圈，複雜度為
O(n)。總複雜度：
O(n)。
空間複雜度
僅使用兩個指標變數，額外空間為常量
O(1)。
總結
本題透過 快慢指標法 高效解決了連結串列入環點的查詢問題。在實際開發中，這種方法不僅可以用於連結串列問題，還可擴充套件到許多類似的迴圈檢測場景。
關鍵點總結：
快慢指標的技巧。
環形結構的性質。
利用數學和邏輯簡化複雜問題。
