检测链表中是否有环:Swift实现

作者:问题终结者2024.01.17 23:02浏览量:2

简介:通过Floyd的环形检测算法(也称为“快慢指针”算法),你可以有效地检测链表中是否存在环。此方法基于一个简单的事实:如果链表中存在环,那么至少有一个指针会陷入这个环中。

千帆应用开发平台“智能体Pro”全新上线 限时免费体验

面向慢思考场景,支持低代码配置的方式创建“智能体Pro”应用

立即体验

在Swift中,我们可以使用两个指针来检测链表中是否存在环。一个快速指针每次移动两步,一个慢速指针每次移动一步。如果链表中存在环,那么快指针最终会追上慢指针。如果链表不存在环,那么快指针将会到达链表的尾部。
下面是一个简单的Swift实现:

  1. public struct ListNode {
  2. public var val: Int
  3. public var next: ListNode?
  4. public init(_ val: Int) {
  5. self.val = val
  6. self.next = nil
  7. }
  8. }
  9. public class Solution {
  10. public func hasCycle(_ head: ListNode?) -> Bool {
  11. var slow = head
  12. var fast = head?.next
  13. while fast != nil && fast!.next != nil {
  14. if slow == fast {
  15. return true
  16. }
  17. slow = slow!.next
  18. fast = fast!.next?.next
  19. }
  20. return false
  21. }
  22. }

在这个代码中,我们首先定义了一个ListNode结构,它代表链表中的一个节点。然后,我们创建了一个名为Solution的类,其中包含一个名为hasCycle的方法,该方法接受一个ListNode类型的参数head,表示链表的头节点。这个方法使用两个指针(slowfast)来检测链表是否有环。如果存在环,那么fast指针将会追上slow指针,方法将返回true。如果链表不存在环,那么方法将返回false

article bottom image

相关文章推荐

发表评论