【leetcode】141. Linked List Cycle 解题报告

判断链表中是否含有环。

方法一

最好的也是大家都知道的方法，用快慢指针法，如果慢指针能遇到快指针说明链表中有环

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False
        slow  =   head
        fast = head.next
        while(fast and slow!=fast):
            slow = slow.next
            if fast.next ==None:
                return False
            fast = fast.next.next
        return fast !=None

但是面试的时候一开始就丢上去最优的方法岂不是自断了后路，后面还说啥。
接下来是两种比较次的方法。

方法二

指针扫描链表，并记录已经访问过的步数，每访问一个新的节点时，假设当前已经访问的节点的个数为count，那么从链表头开始，如果在count-1步数内访问到的节点跟当前节点相同，那么说明链表有环。此方法的时间复杂度为$O(n^{2})$O(n2)

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        index = head
        count = 0
        while(index):
            pNode = head
            c =count
            while(c>1):
                pNode = pNode.next
                if pNode == index:
                    return True
                c-=1
            index = index.next
            count+=1
        return False      

方法三

时间换空间，将访问或的节点放到字典里保存，如果当前访问的节点在字典里，说明重复访问了，即有环，时间空间复杂度都是O(n)

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        pNode = head
        dictionary = {}
        while(pNode):
            if pNode in dictionary:
                return True
            else:
                dictionary[pNode] =  pNode
            pNode = pNode.next
        return False