链表是否有环
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 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)（即，常量）内存解决此问题吗？
解法 1
遍历链表，并将访问过的节点放入哈希表，如果没有重复放入，那么该链表就不是环形链表。
def has_cycle(head):
nodes = set()
while head:
if head in nodes:
return True
nodes.add(head)
head = head.next
return False
执行用时 :44 ms
内存消耗 :18.8 MB
时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中需要花费 O(1) 的时间。
空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多会添加 n 个元素。
解法 2：
通过使用具有不同速度的快、慢两个指针遍历链表，慢指针每次移动一步，而快指针每次移动两步。如果列表存在环，那么两个指针就会在环形部分的某一节点相遇。
def has_cycle(head):
if not head:
return False
slow, fast = head, head.next
while slow and fast and fast.next:
if slow == fast:
return True
slow = slow.next
fast = fast.next.next
return False
执行用时 :40 ms
内存消耗 :18.3 MB
时间复杂度：O(n)，n 为链表中结点数，分别考虑下面两种情况。
-
链表中不存在环：
快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(n)。 -
链表中存在环：
我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分
当慢指针在走完非环部分即将进入环形部分时，快指针已经进入环，当前迭代次数等于慢指针迭代次数，即非环部分长度，记为 N。
接下来，两个指针将都处于环形部分：慢指针每次移动一步，而快指针每次移动两步，其速度的差值为 1，因此需要经过 指针距离/速度差值 次循环，快指针和慢指针即可相遇。这个距离几乎就是环形部分长度，记为 K，且速度差值为 1，因此环形部分迭代次数约等于 K。
所以，在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。
空间复杂度：我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。
