# 檢測`LinkedList`中的無限循環的示例 > 原文： [https://howtodoinjava.com/puzzles/how-to-detect-infinite-loop-in-linkedlist-in-java-with-example/](https://howtodoinjava.com/puzzles/how-to-detect-infinite-loop-in-linkedlist-in-java-with-example/) 這是一個非常常見的面試問題。 詢問您是否有一個只能在一個方向上移動的鏈表，并且如果該鏈表中有一個循環，您將如何檢測到它？ 好吧，如果您不知道答案，那就不要灰心喪氣。 我個人的觀點是，這類問題無法評估候選人的邏輯思維，因為這樣的問題具有非常具體的答案。 您或者知道，或者不知道。 對于這個特定問題，面試官尋找的最佳答案是“[**弗洛伊德循環發現算法**](https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare "Floyd's Cycle-Finding Algorithm")”。 該算法提出了一種解決方案，建議您一次僅具有兩個指針，而不是僅一個遍歷列表的指針。 兩個指針都將從鏈接列表的第一個節點開始，并使用`next`屬性遍歷。 不同之處在于它們在每個步驟中跳躍的節點數。 第一個節點每次跳到下一個節點，另一個節點一次跳兩個節點。 第一個節點稱為**較慢的節點**或**烏龜**，第二個節點**較快的節點**被稱為**兔子**。  龜兔算法 這種遍歷可確保如果鏈接鏈接中存在循環，則兩個節點肯定會在其遍歷路徑中的某處相遇。 它具有`O(n)`復雜度。 讓我們使用 Java 示例代碼對此進行驗證。 我已經寫了一個最少可能的單鏈表代碼，僅用于演示此示例。 ```java package com.howtodoinjava.demo.core; public class SinglyLinkedList { private Node start; public void add(Integer i) { Node node = new Node(i); if(start == null) start = node; else { Node temp = start; while(temp.next != null) { temp = temp.next; } temp.next = node; } } public Node getStart() { return start; } static class Node { Node(Integer i) { this.value = i; } private Integer value; private Node next; public Integer getValue() { return value; } public void setValue(Integer value) { this.value = value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } } ``` 現在，讓我們先在鏈表上進行循環測試，然后再進行循環測試。 ```java package com.howtodoinjava.demo.core; public class FindLoopsInLinkedList { public static void main(String args[]) { FindLoopsInLinkedList finder = new FindLoopsInLinkedList(); SinglyLinkedList sampleList = new SinglyLinkedList(); // First Insert randomly ten elements in a linked list for (int i = 0; i < 10; i++) { sampleList.add(i); } System.out.println("Loop Existence : " + finder.doesLoopExist(sampleList)); System.out.println("Loop Existence : " + finder.doesLoopExist(finder.createLoop(sampleList))); } public boolean doesLoopExist(SinglyLinkedList listToCheck) { SinglyLinkedList.Node tortoise = listToCheck.getStart(); SinglyLinkedList.Node hare = listToCheck.getStart(); try { while (true) { tortoise = tortoise.getNext(); hare = hare.getNext().getNext(); if (tortoise == hare) { return true; } } } catch (NullPointerException ne) { return false; } } private SinglyLinkedList createLoop(SinglyLinkedList sampleList) { sampleList.getStart().getNext().getNext().getNext().setNext(sampleList.getStart().getNext()); return sampleList; } } ``` 在上面的程序中，我們創建了一個鏈接列表，并在該列表中插入了 10 個元素。 否，當我們檢查行號中是否存在循環時。 15 這是錯誤的。 但是，當在第 167 行時，我們在鏈接列表內部創建了一個循環，結果如愿。 上面程序的輸出是這樣的： ```java Loop Existence : false [Line 15] Loop Existence : true [Line 16] ``` 如您所見，只要我們在行號中插入循環。 16，我們的算法實現能夠檢測到它。 學習愉快！