一聋伦、哈希表
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
//方法1. 一次遍歷炮姨，使用HashMap的方法存儲(chǔ)這個(gè)點(diǎn)之前出現(xiàn)過(guò)沒(méi)有
//時(shí)間復(fù)雜度O(N)，控件復(fù)雜度O(1)
//邊界條件
guard var head = head else {
return false
}
var haveSeen = Set<ListNode>()
while head.next != nil {
if !haveSeen.add(head) {
return true
}
head = head.next!
}
return false
}
}
二、快慢指針
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
var slowNode = head
var fastNode = head?.next
while fastNode?.next != nil {
if slowNode === fastNode {
return true
}
slowNode = slowNode?.next
fastNode = fastNode?.next?.next
}
return false
}
}
