一 题目描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。 你能给出空间复杂度O(1)的解法么？
输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试
示例1
输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表,返回true
示例2
输入：{1},-1
返回值：false
说明： 第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3
输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：true
二 解题思路
(一) 双指针
定义两个指针:fast 与 slow: 起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
复杂度分析：
时间复杂度O(N)：其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度
空间复杂度O(1)：额外使用的指针占用常数空间
解题代码:
class Solution:
def hasCycle(self , head ):
# write code here
if not head:
return head
# 双指针 快慢指针
slow = head
fast = head
while slow and fast:
slow = slow.next
if fast.next:
fast = fast.next.next
else:
return False
# 当双指针相遇 即表示指针有环
if slow == fast:
return True
return False
或者
class Solution:
def hasCycle(self , head ):
# write code here
if head == None or head.next == None:
return False
fast = head.next#快指针
slow = head#慢指针
while fast != slow:#快慢指针不相遇就要遍历
if fast == None or fast.next == None:
return False
fast = fast.next.next#快指针移动两格
slow = slow.next#慢指针移动一格
return True
(二) 哈希表(暴力法)[空间复杂度不为O(1)]
遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现
1、创建一个Set集合，用于存放链表结点。
2、遍历链表，并将访问过的结点存储到哈希表中,即插入到set里 。
3、判断当前结点是否在哈希表set中，若存在就代表产生了环，返回 true。如果没在就加入。
4、遍历结束，则返回 false。创建一个Set集合，用于存放链表结点
只要head!=null
从链表头节点开始，将head加入set
head = head.next
如果加入失败，说明该结点已经存在，即证明链表存在环
复杂度分析：
时间复杂度O(N)：其中 N 为链表中节点的数目。遍历整个链表的结点
空间复杂度O(N)：其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
解题代码:
class Solution:
def hasCycle(self , head ):
# write code here
se = set()#定义一个集合
while head != None:#如果头节点不为空，就遍历链表
if head in se:#判断当前节点是否出现过，如果出现过就返回true
return True
se.add(head)#如果没有出现过就插入
head = head.next#head等于下一个节点
return False
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99768.html
