环形链表（力扣100）

最简单的想法就是建一个空集合seen = set()。 然后从头开始走，每走到一个节点，就看看它在不在集合里。时间复杂度为On，空间复杂度为On

更优的方法是使用快慢指针，慢指针slow，每次只走 1 步。快指针fast，每次走 2 步。

如果没有环，fast最终会变成None

如果有环，假设环的长度为C，当slow进入环时，fast在环内某处，距离slow的距离为K，K小于等于C。由于fast相对于slow的速度为1，并且由于slow要C步才能出环，而fast需要K步就能追上slow，所以fast一定会追上slow。

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head==None or head.next==None: return False slow=head fast=head.next while slow and fast: if slow==fast: return True slow=slow.next fast=fast.next if fast==None: return False else: fast=fast.next return False