内容简介：版权声明： 本文为博主原创文章，发表自知一的指纹。转载需向给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
版权声明： 本文为博主原创文章，发表自知一的指纹。转载需向 我的邮箱 申请。
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
正常的解题思路，通过记录走过的节点来判断是否有环。
时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1) 的时间。
空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多可以添加 n 个元素。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<Integer> points = new HashSet<Integer>();
ListNode cur = head;
while (null != cur){
int curHashCode = cur.hashCode();
if(points.contains(curHashCode)){
return true;
}
points.add(curHashCode);
cur = cur.next;
}
return false;
}
}
第二种解题思路是双指针大小步，一个指针每次走一步，另一个指针每次走两步，如果有环的话则两个指针最终会相遇。
在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。
空间复杂度：O(1)，我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (null == head){
return false;
}else if (null == head.next){
return false;
}else if (head == head.next.next){
return true;
}
ListNode minCur = head.next;
ListNode maxCur = head.next.next;
while (minCur != maxCur){
if (null == minCur.next){
return false;
}else if (null == maxCur.next){
return false;
}else if (null == maxCur.next.next){
return false;
}
minCur = minCur.next;
maxCur = maxCur.next.next;
if (minCur == maxCur){
return true;
}
}
return false;
}
}
如果此文章能给您带来小小的提升，不妨小额赞赏我一下，以鼓励我写出更好的文章！
微信打赏
支付宝打赏
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- LeetCode 141——环形链表
- Canvas环形倒计时组件
- 利用canvas实现环形进度条
- 使用Golang实现双向环形链表
- 一起撸个环形 Android 图表
- Principle教程：如何完成数字变化+环形加载？
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
