Linked List Cycle

2013 年 2 月 4 日

时间复杂度: O(n), 空间复杂度: O(1)

解题思路

这是一道经典的链表题目 – 环形链表，基本的解题思路是双指针技巧里面的快慢指针。

如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少？
一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

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 {
        if head == nil || head?.next == nil {
            return false
        }
        var slow = head
        var fast = head?.next
        
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast {
                return true
            }
        }
        return false
    }
}

About The Author

stack