在此示例中，我們將學(xué)習(xí)Java中的檢測LinkedList中是否存在循環(huán)。
要理解此示例，您應(yīng)該了解以下Java編程主題：
class LinkedList {
//創(chuàng)建Node類的對象
//表示鏈表的頭部
Node head;
//靜態(tài)內(nèi)部類
static class Node {
int value;
//將每個節(jié)點連接到下一個節(jié)點
Node next;
Node(int d) {
value = d;
next = null;
}
}
//檢查是否存在循環(huán)
public boolean checkLoop() {
//在LinkedList的開頭創(chuàng)建兩個引用
Node first = head;
Node second = head;
while(first != null && first.next !=null) {
//將第一個引用移動2個節(jié)點
first = first.next.next;
//將第二個引用移動1個節(jié)點
second = second.next;
//如果兩個引用相等（遇）
if(first == second) {
return true;
}
}
return false;
}
public static void main(String[] args) {
//創(chuàng)建LinkedList的對象
LinkedList linkedList = new LinkedList();
//為每個鏈表節(jié)點賦值
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
//將鏈表的每個節(jié)點連接到下一個節(jié)點
linkedList.head.next = second;
second.next = third;
third.next = fourth;
//在LinkedList中進(jìn)行循環(huán)
fourth.next = second;
//打印節(jié)點值
System.out.print("LinkedList: ");
int i = 1;
while (i <= 4) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
i++;
}
//調(diào)用方法檢查循環(huán)
boolean loop = linkedList.checkLoop();
if(loop) {
System.out.println("\n在 LinkedList 中有一個循環(huán).");
}
else {
System.out.println("\nLinkedList中沒有循環(huán).");
}
}
}輸出結(jié)果
LinkedList: 1 2 3 4 在 LinkedList 中有一個循環(huán).
在上面的示例中，我們已經(jīng)用Java 實現(xiàn)了LinkedList。我們使用了Floyd的循環(huán)查找算法來檢查 LinkedList 中是否存在循環(huán)。
注意checkLoop()方法中的代碼。在這里，我們有兩個名為first，second的變量，它們遍歷LinkedList中的節(jié)點。
first - 在單次迭代中使用2個節(jié)點進(jìn)行遍歷
second - 在單次迭代中使用1個節(jié)點進(jìn)行遍歷。
兩個節(jié)點以不同的速度遍歷。 因此，如果LinkedList中有循環(huán)，它們將相遇。