Python 鏈表中間是否有環(huán) Leetcode No.141

Ps：用英語的不是為了裝哈，主要是為了鍛煉一下英語閱讀，畢竟想往上走的話，讀源碼，讀文檔，讀國外論文都是必經(jīng)之路。那么英語能力必不可少，希望你們也可以想我一樣。
主要意思就是判斷鏈表中是否有環(huán)。

思路也很簡單：一個是用set存，發(fā)現(xiàn)他數(shù)量不加了那不就代表有環(huán)了嘛。
第二種方式非常的巧妙，用一個快指針和一個慢指針，就等于是一個龜兔賽跑，兔子是快指針，龜是慢指針，只要是個鏈表沒有環(huán)，兔子肯定跑的快，這種方法優(yōu)點是空間復(fù)雜度為O（1）

            
              
                #第一種方法，借用了set的數(shù)據(jù)結(jié)構(gòu)
              
              
                # 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
        """
              
              
        a 
              
                =
              
              
                set
              
              
                (
              
              
                )
              
              
        p 
              
                =
              
               head
        
              
                while
              
               p 
              
                and
              
               p
              
                .
              
              
                next
              
              
                :
              
              
            lenth1 
              
                =
              
              
                len
              
              
                (
              
              a
              
                )
              
              
            a
              
                .
              
              add
              
                (
              
              
                id
              
              
                (
              
              p
              
                )
              
              
                )
              
              
            lenth2 
              
                =
              
              
                len
              
              
                (
              
              a
              
                )
              
              
                if
              
               lenth2
              
                ==
              
              lenth1
              
                :
              
              
                return
              
              
                True
              
              
            p 
              
                =
              
               p
              
                .
              
              
                next
              
              
                return
              
              
                False
              
              
                #第二種方法
              
              
                # 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
        """
              
              
        fast 
              
                =
              
               slow 
              
                =
              
               head
        
              
                while
              
               slow 
              
                and
              
               fast 
              
                and
              
               fast
              
                .
              
              
                next
              
              
                :
              
              
            slow 
              
                =
              
               slow
              
                .
              
              
                next
              
              
            fast 
              
                =
              
               fast
              
                .
              
              
                next
              
              
                .
              
              
                next
              
              
                if
              
               slow 
              
                is
              
               fast
              
                :
              
              
                return
              
              
                True
              
              
                return
              
              
                False
              
            
          

第二種方法的算法時間分析：