内容简介：版权声明： 本文为博主原创文章，发表自知一的指纹。转载需向给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 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教程：如何完成数字变化+环形加载？
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Reversing
艾拉姆（Eilam,E.） / 韩琪、杨艳、王玉英、李娜 / 电子工业出版社 / 2007-9 / 79.00元
本书描述的是在逆向与反逆向之间展开的一场旷日持久的拉锯战。作者Eldad Eilam以一个解说人的身份为我们详尽地评述了双方使用的每一招每一式的优点与不足。 书中包含的主要内容有：操作系统的逆向工程；.NET平台上的逆向工程；逆向未公开的文件格式和网络协议；逆向工程的合法性问题；拷贝保护和数字版权管理技术的逆向工程；防止别人对你的代码实施逆向工程的各种技术；恶意程序的逆向工程；反编译器的基本......一起来看看 《Reversing》 这本书的介绍吧!
