环形链表（力扣100）

最简单的想法就是建一个空集合seen set()。 然后从头开始走每走到一个节点就看看它在不在集合里。时间复杂度为On空间复杂度为On更优的方法是使用快慢指针慢指针slow每次只走 1 步。快指针fast每次走 2 步。如果没有环fast最终会变成None如果有环假设环的长度为C当slow进入环时fast在环内某处距离slow的距离为KK小于等于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 headNone or head.nextNone: return False slowhead fasthead.next while slow and fast: if slowfast: return True slowslow.next fastfast.next if fastNone: return False else: fastfast.next return False