Java 检测链表中的循环

在本文章中，我们将了解如何检测链表中的循环。链表是一系列通过链接连接在一起的数据结构。链表是包含项目的链接序列。每个链接包含到另一个链接的连接。

下面是相同内容的示例−

假设我们的输入是 -

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 elements of the linked list are: 45 60 75 90
There is a loop in the linked list.