Java程序检测链表中的循环

---

什么是链表？

一个链表是由一系列数据结构组成的序列，每个节点包含两部分：

• 数据 - 存储在节点中的值或信息。
  
• 下一个 - 指向序列中下一个节点的引用（或指针）。

链表中的循环是什么？

循环意味着链表的最后一个节点连接回链表中较早的节点，从而创建一个循环。这会导致在列表操作期间出现无限遍历。

检测循环的不同方法

以下是检测链表中是否存在循环的不同方法：

• 使用HashSet检测循环
  
• 使用Floyd循环检测算法检测循环

使用HashSet检测循环

HashSet：HashSet是Java中实现Set接口的集合类。它是java.util包的一部分，用于存储唯一元素的集合。

步骤1 - 节点创建

• Node类用于定义链表中每个节点的结构。每个节点包含两个组件：data用于保存值，next用于指向列表中后续节点。

步骤2 - 链表构建

• push方法用于在链表的头部插入新节点。这允许添加元素，同时保持链表的结构。

步骤3 - 使用HashSet检测循环

• check_loop方法使用HashSet来检测链表中的循环。在遍历列表时，每个节点都会与HashSet进行检查。如果某个节点已存在于集合中，则表示存在循环，方法返回true。如果节点不存在，则将其添加到集合中，并继续遍历。如果遍历结束(head == null)，则方法返回false，确认不存在循环。

使用HashSet的Java程序来检测链表中的循环

以下是使用HashSet检测链表中循环的示例：

import java.util.*;
public class Demo {
	static Node head;
	static class Node {
		int data;
		Node next;
		Node(int d) {   //  Node creation
			data = d;
			next = null;
		}
	}
	static public void push(int new_data) { // Linked List Construction
		Node new_node = new Node(new_data);
		new_node.next = head;
		head = new_node;
	}                                                                                                                 
	static boolean check_loop(Node head) {    // Loop Detection Using HashSet
		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

使用Floyd循环算法检测循环

Floyd循环检测算法，也称为龟兔算法，是一种用于检测链表或序列中循环的方法。

它使用两个指针

• 慢指针一次移动一步。
  
• 快指针一次移动两步。

在这个算法中，一个指针一次移动一步（慢），另一个指针一次移动两步（快）。如果列表中存在循环，则快指针将在循环内与慢指针相遇。

• check_loop方法使用两个指针first_node和second_node来检测循环。
  
• first_node一次移动两步，second_node一次移动一步。
  
• 如果这两个指针在任何时候相遇，则确认存在循环。
• 如果first_node到达列表的末尾（null），则表示不存在循环，方法返回false。

使用Floyd循环检测算法的Java程序来检测链表中的循环

以下是使用Floyd循环检测算法检测链表中循环的示例：

public class Demo {
	Node head;
	static class Node {
		int value;
		Node next;
		Node(int d) {       // Constructor to initialize the node
			value = d;
			next = null;
		}
	}
	public boolean check_loop() {   //using Floyd's Cycle Detection
		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.