Java 程序:检测 LinkedList 中的循环
要理解这个示例,你需要了解以下 Java 编程 主题:
示例:在 LinkedList 中检测循环
class LinkedList {
// 创建 Node 类的对象
// 代表链表的头部
Node head;
// 静态内部类
static class Node {
int value;
// 将每个节点连接到下一个节点
Node next;
Node(int d) {
value = d;
next = null;
}
}
// 检查是否存在循环
public boolean checkLoop() {
// 在链表开始处创建两个引用
Node first = head;
Node second = head;
while(first != null && first.next !=null) {
// 将 first 引用移动 2 个节点
first = first.next.next;
// 将 second 引用移动 1 个节点
second = second.next;
// 如果两个引用相遇
// 则存在循环
if(first == second) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// 创建 LinkedList 的对象
LinkedList linkedList = new LinkedList();
// 为每个链表节点赋值
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
// 将链表的每个节点连接到下一个节点
linkedList.head.next = second;
second.next = third;
third.next = fourth;
// 在 LinkedList 中制造循环
fourth.next = second;
// 打印节点值
System.out.print("LinkedList: ");
int i = 1;
while (i <= 4) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
i++;
}
// 调用方法检查循环
boolean loop = linkedList.checkLoop();
if(loop) {
System.out.println("\nLinkedList 中存在循环。");
}
else {
System.out.println("\nLinkedList 中不存在循环。");
}
}
}