看到题目的第一反应就是集合记录已访问的节点,然而在Swift
中,ListNode
对象并未实现Hashable
协议。
解法一:双指针
通过定义slow和fast指针,slow每走一步,fast走两步,若是有环,则一定会在环的某个结点处相遇。
func hasCycle ( _ head: ListNode?) -> Bool {
var slow = head, fast = head
while fast != nil && fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}
注意此处,slow与fast是否相等使用===判断,同样因为ListNode并未实现Hashable
协议。而考虑到可以使用===判断指针,那么,可以使用数组保存已访问的节点。
解法二:HashTable
func hasCycle ( _ head: ListNode?) -> Bool {
guard var current = head else { return false }
var visited = [ListNode]()
while current.next != nil {
if visited.contains(where: { $0 === current }) {
return true
} else {
visited.append(current)
current = current.next!
}
}
return false
}