给定一个单链表,判断链表中是否有环的几种方法
![在这里插入图片描述](https://img-blog.csdnimg.cn/2019030922592992.png)
今天刷LeetCode刷到一道这样的题,详情参见(环形链表)
ADT:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
方法一:循环遍历节点,遍历一个便标记一个,遍历过程判断是否被标记,若已被标记则表示有环
方法说明:头指针移动,若到达之前到达过的位置则表示有环,若无环则会走到链表末端。
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while(head!=null) {
if(set.contains(head)) {
return true;
}else {
set.add(head);
head = head.next;
}
}
return false;
}
}
方法二:声明两个指针,一个指针走一次经过两个节点(快指针quick),另一个走一次经过一个节点(慢指针slow)
方法说明:快指针走的比较快,若链表有环,则一定会追上慢指针,若无环,则会走到链表末端。
public class Solution {
public boolean hasCycle(ListNode head) {
==
ListNode quick = head;
ListNode slow = head;
while(quick!=null&&quick.next!=null){
quick = quick.next.next;
slow = slow.next;
if(quick==slow){
return true;
}
}
return false;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)