检测链表中是否有环:Swift实现
2024.01.17 23:02浏览量:2简介:通过Floyd的环形检测算法(也称为“快慢指针”算法),你可以有效地检测链表中是否存在环。此方法基于一个简单的事实:如果链表中存在环,那么至少有一个指针会陷入这个环中。
千帆应用开发平台“智能体Pro”全新上线 限时免费体验
面向慢思考场景,支持低代码配置的方式创建“智能体Pro”应用
在Swift中,我们可以使用两个指针来检测链表中是否存在环。一个快速指针每次移动两步,一个慢速指针每次移动一步。如果链表中存在环,那么快指针最终会追上慢指针。如果链表不存在环,那么快指针将会到达链表的尾部。
下面是一个简单的Swift实现:
public struct ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
public class Solution {
public func hasCycle(_ head: ListNode?) -> Bool {
var slow = head
var fast = head?.next
while fast != nil && fast!.next != nil {
if slow == fast {
return true
}
slow = slow!.next
fast = fast!.next?.next
}
return false
}
}
在这个代码中,我们首先定义了一个ListNode
结构,它代表链表中的一个节点。然后,我们创建了一个名为Solution
的类,其中包含一个名为hasCycle
的方法,该方法接受一个ListNode
类型的参数head
,表示链表的头节点。这个方法使用两个指针(slow
和fast
)来检测链表是否有环。如果存在环,那么fast
指针将会追上slow
指针,方法将返回true
。如果链表不存在环,那么方法将返回false
。

发表评论
登录后可评论,请前往 登录 或 注册