ในบทความนี้ เราจะเข้าใจวิธีการตรวจหาลูปใน LinkedList รายการที่เชื่อมโยงเป็นลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อกันผ่านลิงก์ รายชื่อที่เชื่อมโยงคือลำดับของลิงก์ซึ่งมีรายการต่างๆ แต่ละลิงก์มีการเชื่อมต่อกับลิงก์อื่น
ด้านล่างนี้เป็นการสาธิตสิ่งเดียวกัน -
สมมติว่าข้อมูลที่เราป้อนคือ −
Run the program
ผลลัพธ์ที่ต้องการจะเป็น −
The loop exists in the linked list
อัลกอริทึม
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
ตัวอย่างที่ 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("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");
}
} ผลลัพธ์
The required packages have been imported The loop exists in the linked list
ตัวอย่างที่ 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("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.");
}
}
} ผลลัพธ์
The required packages have been imported The loop exists in the linked list
