切換語言為:簡體

Swift 實現查詢連結串列入環點:快慢指標法

  • 爱糖宝
  • 2024-11-24
  • 2027
  • 0
  • 0

摘要

連結串列問題中,查詢環的起始節點是一個經典的進階題目。本篇文章將講解如何在 Swift 中實現 查詢連結串列入環點 的演算法,並透過 快慢指標法 實現 O(1) 空間複雜度,詳細分析程式碼邏輯並給出完整的測試案例。

描述

給定一個連結串列的頭節點  head ,返回連結串列開始入環的第一個節點。 如果連結串列無環,則返回 null

如果連結串列中有某個節點,可以透過連續跟蹤 next 指標再次到達,則連結串列中存在環。 爲了表示給定連結串列中的環,評測系統內部使用整數 pos 來表示連結串列尾連線到連結串列中的位置(索引從 0 開始)。如果 pos 是 -1,則在該連結串列中沒有環。注意:pos 不作為引數進行傳遞,僅僅是爲了標識連結串列的實際情況。

不允許修改 連結串列。

示例 1:

Swift 實現查詢連結串列入環點:快慢指標法

輸入: head = [3,2,0,-4], pos = 1
輸出: 返回索引為 1 的連結串列節點
解釋: 連結串列中有一個環,其尾部連線到第二個節點。

示例 2:

Swift 實現查詢連結串列入環點:快慢指標法

輸入: head = [1,2], pos = 0
輸出: 返回索引為 0 的連結串列節點
解釋: 連結串列中有一個環,其尾部連線到第一個節點。

示例 3:

Swift 實現查詢連結串列入環點:快慢指標法

輸入: head = [1], pos = -1
輸出: 返回 null
解釋: 連結串列中沒有環。

提示:

  • 連結串列中節點的數目範圍在範圍 [0, 104] 內

  • -105 <= Node.val <= 105

  • pos 的值為 -1 或者連結串列中的一個有效索引

進階: 你是否可以使用 O(1) 空間解決此題?

題解答案

我們採用 快慢指標法 解決該問題。
在之前判斷連結串列是否存在環的基礎上,進一步確定環的起始節點。

核心思路:

  1. 使用快慢指標判斷連結串列是否有環。

  2. 若有環,快慢指標相遇時,將其中一個指標重新指向連結串列頭節點,並保持另一個指標在相遇點。

  3. 兩個指標以相同的速度前進,相遇時的節點即為入環點。

題解程式碼

以下是 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
}

題解程式碼分析

  1. 快慢指標的初始化

    • 慢指標每次走一步,快指標每次走兩步。

    • 快指標達到連結串列末尾時(fast == nilfast.next == nil),說明連結串列無環。

  2. 檢測環的存在

    • 若快慢指標在某個節點相遇,則連結串列中存在環。

    • 慢指標和快指標的路徑會在環中迴圈,從而必定相遇。

  3. 確定環的起始節點

    • 相遇後,將其中一個指標(如 pointer1)重新指向連結串列頭節點,另一個指標(如 pointer2)保持在相遇點。

    • 兩個指標每次走一步,最終相遇時的節點即為環的起始節點。

  4. 時間複雜度

    • 檢測環的階段:O(n),連結串列節點最多被訪問兩次。

    • 找入環點的階段:O(n),快慢指標最多走一圈。

    • 總時間複雜度:O(n)

  5. 空間複雜度

    • 只使用了兩個指標,空間複雜度為 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)

總結

本題透過 快慢指標法 高效解決了連結串列入環點的查詢問題。在實際開發中,這種方法不僅可以用於連結串列問題,還可擴充套件到許多類似的迴圈檢測場景。

關鍵點總結:

  • 快慢指標的技巧。

  • 環形結構的性質。

  • 利用數學和邏輯簡化複雜問題。

0則評論

您的電子郵件等資訊不會被公開,以下所有項目均必填

OK! You can skip this field.