题目

环形链表 1

问题:

给定一个链表，判断链表中是否有环。

说明:

你能否不使用额外空间解决此题？

解题思路:

双指针法：

在找链表中点时用过的快慢指针，如果有环的话，快指针总会和慢指针相遇

哈希表法：

使用一个指针遍历链表，每次访问一个节点首先都判断Hashset中是否存在同一个节点，如果存在则链表存在环，否则持续加入到Hashset中。当指针遍历到NULL的时候仍然没有找到环，证明链表不存在环。 但不满足条件。

代码：

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}

extension SingNode : CustomStringConvertible {
    public var description: String {
        var string = "\(value)"
        var node = self.nextNode
        
        while node != nil {
            string = string + " -- " + "\(node!.value)"
            node = node?.nextNode
        }
        return string
    }
}
 **/
      
       func hasCycleI(_ l1:SingNode?) -> Bool {
        if l1 == nil || l1?.nextNode == nil {
            return false
        }
        var fast = l1
        var slow = l1
        
        while fast?.nextNode != nil && fast?.nextNode?.nextNode != nil {
            fast = fast?.nextNode?.nextNode
            slow = slow?.nextNode
            if fast == slow {
                return true
            }
        }
        return false
    }