Python 链表中间是否有环 Leetcode No.141
Ps：用英语的不是为了装哈，主要是为了锻炼一下英语阅读，毕竟想往上走的话，读源码，读文档，读国外论文都是必经之路。那么英语能力必不可少，希望你们也可以想我一样。
主要意思就是判断链表中是否有环。
思路也很简单：一个是用set存，发现他数量不加了那不就代表有环了嘛。
第二种方式非常的巧妙，用一个快指针和一个慢指针，就等于是一个龟兔赛跑，兔子是快指针，龟是慢指针，只要是个链表没有环，兔子肯定跑的快，这种方法优点是空间复杂度为O（1）
#第一种方法，借用了set的数据结构
# 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
第二种方法的算法时间分析：
