141.环形链表

一、哈希表

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的方法存储这个点之前出现过没有
        //时间复杂度O(N)，控件复杂度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
    }
}