Java 程序检测 LinkedList 中的循环
javacampus interviewserver side programmingprogramming
在本文中，我们将了解如何检测 LinkedList 中的循环。链表是一系列数据结构，它们通过链接连接在一起。链表是包含项目的链接序列。每个链接都包含与另一个链接的连接。
下面是相同的演示 −
假设我们的输入是 −
Run the program
期望的输出将是 −
链接列表中存在循环
算法
步骤 1 - 开始 步骤 2 - 声明 步骤 3 - 定义值。 步骤 4 - 定义具有相关成员的类。 步骤 5 - 创建类的实例，并初始化节点。 步骤 6 - 定义函数以检查是否为循环。 步骤 7 - 为此，创建一个 HashSet，并将元素添加到最顶层节点。 步骤 8 - 每次迭代后将节点指向下一个元素。 步骤 9 - 在主方法中，创建一个实例并使用‘push’方法将元素添加到列表中。 步骤 10 - 调用‘check_loop’方法，并在控制台上显示相关信息。 第 11 步 - 停止
示例 1
这里我们使用遍历方法来找到循环。
import java.util.*;
public class Demo {
static Node head;
static class Node {
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
static public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
static boolean check_loop(Node head){
HashSet<Node> s = new HashSet<Node>();
while (head != null) {
if (s.contains(head))
return true;
s.add(head);
head = head.next;
}
return false;
}
public static void main(String[] args){
System.out.println("所需包已导入");
Demo input_list = new Demo();
input_list.push(45);
input_list.push(60);
input_list.push(75);
input_list.push(90);
input_list.head.next.next.next.next = input_list.head;
if (check_loop(head))
System.out.println("链表中存在循环");
else
System.out.println("循环在链接列表中不存在");
}
}
输出
所需的包已导入 循环在链接列表中存在
示例 2
在这里，我们将操作封装成展现面向对象编程的函数。
public class Demo {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public boolean check_loop() {
Node first_node = head;
Node second_node = head;
while(first_node != null && first_node.next !=null) {
first_node = first_node.next.next;
second_node = second_node.next;
if(first_node == second_node) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Demo input_list = new Demo();
input_list.head = new Node(45);
Node second_node = new Node(60);
Node third_node = new Node(75);
Node fourth_node = new Node(90);
input_list.head.next = second_node;
second_node.next = third_node;
third_node.next = fourth_node;
fourth_node.next = second_node;
System.out.print("链接列表的元素为:");
int i = 1;
while (i <= 4) {
System.out.print(input_list.head.value + " ");
input_list.head = input_list.head.next;
i++;
}
boolean loop = input_list.check_loop();
if(loop) {
System.out.println("\n链接列表中有一个循环。");
}
else {
System.out.println("\n链接列表中没有循环。");
}
}
}
输出
链表元素为:45 60 75 90 链表存在循环。
