141. 环形链表(easy)

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶
你能用 O(1)（即，常量）内存解决此问题吗？

• show the code:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#### code1(hash)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        dic = {head}
        while head:
            head = head.next
            if head not in dic:
                dic.add(head)
            else:
                return True
        return False
### code2(two pointers)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        slow = head
        quick = head.next
        while slow != quick:
            if not quick or not quick.next:
                return False
            slow = slow.next
            quick = quick.next.next
        return True

• 此题有两种方法：一种是建立一个集合来存储先前遍历过的节点，也就是哈希法，如果之后出现重复的节点，那么可以判断链表中存在环（注意这里集合存储的是节点内存地址而不是节点值）
• 由于题目进阶版要求的空间复杂度，所以哈希表肯定是不行的，不使用额外空间的话考虑使用快慢指针法，所谓的快慢指针就是指两个指针，一个指针一次走一步即慢指针，一个一次走两步即快指针，也是这种链表问题的常见方法。我们知道如果链表中存在环，那么快慢指针一定会相遇，至于什么时候相遇，我们可以近似认为这取决于环的长度。如果两指针相遇，则说明存在环，如果遍历到null，说明不存在环。
• 有关时间和空间复杂度看官方题解分析：
• 复杂度分析