有一個單向連結清單,連結清單中可能出現“環”,那麼,如何用程式來判斷該連結清單是否為有環連結清單呢?
/**
* @Author: subd
* @Date: 2019/9/4 7:02
*/
public class SingleLinkNode {
/**
* 連結清單節點
*/
private static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
/**
* 判斷是否有環
*
* @param head 連結清單頭結點
* @return
*/
public static boolean isCycle(Node head) {
Node p1 = head;
Node p2 = head;
int step = 0;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Node node1 = new Node(5);
Node node2 = new Node(3);
Node node3 = new Node(2);
Node node4 = new Node(7);
Node node5 = new Node(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node2;
System.out.println(isCycle(node1));
}
}