Trong bài viết này, chúng ta sẽ hiểu cách phát hiện vòng lặp trong LinkedList. Danh sách được liên kết là một chuỗi các cấu trúc dữ liệu, được kết nối với nhau thông qua các liên kết. Danh sách được Liên kết là một chuỗi các liên kết chứa các mục. Mỗi liên kết chứa một kết nối đến một liên kết khác.
Dưới đây là một minh chứng về điều tương tự -
Giả sử đầu vào của chúng tôi là -
Run the program
Đầu ra mong muốn sẽ là -
The loop exists in the linked list
Thuật toán
Step 1 - START Step 2 - Declare namely Step 3 - Define the values. Step 4 - Define the class with the relevant members. Step 5 - Create an instance of the class, and initialize the nodes. Step 6 - Define functions to check if it is a loop. Step 7 - For this, create a HashSet, and add elements to the topmost node. Step 8 - Point the node to the next element after every iteration. Step 9 - In the main method, create an instance and add elements to the list using the ‘push’ method. Step 10 - Call the ‘check_loop’ method, and display the relevant message on the console. Step 11 - Stop
Ví dụ 1
Ở đây, chúng tôi sử dụng phương pháp duyệt để tìm vòng lặp.
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("The required packages have been imported");
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("The loop exists in the linked list");
else
System.out.println("The loop doesnot exists in the linked list");
}
} Đầu ra
The required packages have been imported The loop exists in the linked list
Ví dụ 2
Ở đây, chúng tôi đóng gói các hoạt động thành các hàm trưng bày lập trình hướng đối tượng.
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("The elements of the linked list are: ");
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("\nThere is a loop in the linked list.");
}
else {
System.out.println("\nThere is no loop in the linked list.");
}
}
} Đầu ra
The required packages have been imported The loop exists in the linked list