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.