网站必须做ipv6,公司专业做网站,网站建设项目费用报价,无锡个人网站制作链表有环的情况一般是链表的尾指向前面的节点而不是null#xff0c;如head-node1-node2-node3-node4-tail-node2#xff0c;该链表存在环。判断环是否存在可以借助两个指针#xff0c;一个指针每次迭代只移动一步#xff0c;第二个指针每次迭代移动… 链表有环的情况一般是链表的尾指向前面的节点而不是null如head-node1-node2-node3-node4-tail-node2该链表存在环。判断环是否存在可以借助两个指针一个指针每次迭代只移动一步第二个指针每次迭代移动两步。如果存在环两个指针最终一定会相撞的即指向同一个节点。其它情况则说明环不存在比如两个指针中的任一个指向null。代码如下Node.javapublic class Node {
public char data;
public Node next;
public Node(char data, Node next)
{
this.data data;
this.next next;
}
public Node(char data)
{
this.data data;
this.next null;
}
}LinkedListLoop.javaimport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class LinkedListLoop {
private Node head;
private Node tail;
public LinkedListLoop() {
this.head null;
this.tail null;
}
public boolean isEmpty() {
return (this.head null);
}
public void CreateLinkedList() {
BufferedReader br new BufferedReader(new InputStreamReader(System.in));
String str null;
Node node null;
char data;
try {
str br.readLine();
}catch (IOException e) {
e.printStackTrace();
}
for(int i0; istr.length(); i) {
data str.charAt(i);
if(data ! ) {
node new Node(data);
if(i0) {
head node;
tail node;
}
else {
tail.next node;
tail node;
}
}
}
}
public Node nodeAt(int i) {
Node node head;
int pos 0;
while(node!null) {
if(posi) break;
pos;
node node.next;
}
return node;
}
public void createLoop(int i) {
Node node nodeAt(i);
if(nodenull) return;
tail.next node;
}
public void destroyLoop() {
tail.next null;
}
public boolean hasNode()
{
Node p1 head;
Node p2 head;
while(p1!null) {
p1 p1.next;
p2 p2.next;
if(p2null) return false;
p2 p2.next;
if(p2null) return false;
if(p2 p1) return true;
}
return false;
}
}TestDriver.javapublic class TestDriver {
public static void main(String arg[]) {
LinkedListLoop forTest new LinkedListLoop();
forTest.CreateLinkedList();
if(forTest.hasNode()) System.out.println(It has loop!);
else System.out.println(It has no loop.);
forTest.createLoop(3);
if(forTest.hasNode()) System.out.println(It has loop!);
else System.out.println(It has no loop.);
forTest.destroyLoop();
if(forTest.hasNode()) System.out.println(It has loop!);
else System.out.println(It has no loop.);
}
}测试例子 转载于:https://blog.51cto.com/5372221/1312275
