摘要：初始化时指针走两步，指针走一步，不停遍历的变化最后快慢指针又相遇了，循环结束，代码实现如下复杂度分析，假设链表长度为时间复杂度，链表无环时，快指针会先到达尾部，时间就是如果有环，那么假设环部长度为，时间就是，也就是空间复杂度
上一篇文章我们分析了下链表之反转单向链表，这篇文章我们来分析下另外一个关于链表的经典题目。
判断链表是否有环(在leetcode上的题目地址：环形链表)
题目描述
给定一个链表，判断链表中是否有环
解决方案
一、可以使用hash表来实现，遍历链表，每个节点放入hash表中，如果hash表中包含了某个节点，那么说明有重复节点存在，即是有环。如果没环，那么链表会遍历结束。代码如下：
public static > boolean hasCycle1(Node head) {
HashSet> set = new HashSet<>();
for(Node n=head;n!=null;n=n.getNext()) {
if(set.contains(n)) {
return true;
}
set.add(n);
}
return false;
}
备注Node类参照上篇文章
复杂度分析，假设链表长度为n
时间复杂度：每个元素都要遍历一遍，所以时间为O(n)，每次访问hash表时间为O(1)。
空间复杂度：O(n)，n个元素都会添加到hash表中。
二、上面这种方法可以解决，但是需要借助额外的空间复杂度，能否不使用额外空间解决此题呢？答案是有的，使用快慢指针，想象下，两个人在一个环形跑道上赛跑，跑得快的一定会追上跑的慢的那个人吧。下面用图示来展示下整个过程。
初始化时：
fast指针走两步，slow指针走一步，不停遍历的变化：
最后快慢指针又相遇了，循环结束，代码实现如下：
public static > boolean hasCycle(Node head) {
if(head == null || head.getNext() == null) {
return false;
}
Node slow = head;
Node fast = head;
while(fast != null && fast.getNext() != null) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if(slow == fast) {
return true;
}
}
return false;
}
复杂度分析，假设链表长度为n
时间复杂度：O(n)，链表无环时，快指针会先到达尾部，时间就是O(n)；如果有环，那么假设环部长度为K，时间就是O(n+k)，也就是O(n)
空间复杂度：O(1)
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/71735.html
