判断链表是否有环（Java实现）

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

解题思路：设置两个指针，slow和fast，fast每次走两步，slow每次走一步，如果有环的话fast一定会追上slow，判断fast==slow或者fast.next==slow即可判断

class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}


public class test1 {
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null){
//头指针为空或者只有头节点，无环
return false;
}
ListNode slow,fast = new ListNode(0);
slow = head.next;
fast = head.next.next;
while(true){
if(fast==null||fast.next==null){
//fast走到链表尾
return false;
}else if(fast.next==slow || fast==slow){
return true;
}else{
slow = slow.next;// slow每次走一步
fast = fast.next.next;//fast每次走两步
}
}
}

public static void main(String[] args) {
ListNode node1 = new ListNode(1),node2 = new ListNode(2),node3 = new ListNode(3),node4=new ListNode(4);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node1;
test1 test = new test1();
System.out.println(test.hasCycle(node1));
}
}

 

唯有热爱方能抵御岁月漫长。