判断链表中是否有环,java
给定一个链表,判断链表中是否有环。如果存在环,返回true,否则返回false。
package leecode刷题数据结构与算法;
import java.util.HashSet;
import java.util.Set;
public class 判断是否存在环 {
static class ListNode{
int val;
ListNode next;
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}
public static void main(String[] args){
ListNode node5=new ListNode(5,null);
ListNode node4=new ListNode(4,node5);
ListNode node3=new ListNode(3,node4);
ListNode node2=new ListNode(2,node3);
ListNode node1=new ListNode(1,node2);
node5.next=node4;
System.out.println(hasCycle(node1));
System.out.println(hasCycle2(node1));
}
public static boolean hasCycle(ListNode head){
Set<ListNode> set=new HashSet<ListNode>();
while(head!=null){
if(!set.add(head)){
return true;
}
head=head.next;
}
return false;
}
public static boolean hasCycle2(ListNode head) {
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode quick=head.next;
while(slow!=quick){
if(quick==null||quick.next==null){
return false;
}
slow=slow.next;
quick=quick.next.next;
}
return true;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)