Это очень распространенный вопрос на собеседовании. Нас спрашивают, есть ли у нас связанный список, по которому мы можем перемещаться только в одном направлении, и если в этом связанном списке есть цикл, как мы его обнаружим?
Ну, если вы не знаете ответа, то не расстраивайтесь. Мое личное мнение, что такой вопрос не оценивает логическое мышление кандидата, потому что такие проблемы имеют очень конкретный ответ. Либо вы его знаете, либо нет.
1. Поиск бесконечного цикла в LinkedList
Для этого конкретного вопроса лучшим ответом, который ищет интервьюер, является « Алгоритм поиска цикла Флойда ». Этот алгоритм предлагает решение, в котором вместо одного указателя для обхода списка, нам рекомендуется иметь два указателя одновременно. Оба указателя будут начинаться с первого узла связанного списка и проходить с использованием следующего атрибута.
Разница заключается в количестве узлов, которые они перепрыгивают на каждом шаге. Первый узел перепрыгивает на следующий узел каждый раз, тогда как другой узел перепрыгивает через два узла за раз. Первый узел называется более медленным узлом или «черепахой», а второй более быстрый узел называется «зайцем».
Этот обход гарантирует, что если в связанном списке есть цикл, то оба узла обязательно встретятся где-то на своем пути обхода. Он имеет сложность O(n).
2. Демонстрация
Давайте проверим это с помощью программы 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;}}}Теперь давайте протестируем вышеприведенный связанный список сначала без цикла, а затем с циклом внутри него. Мы используем createLoop() для вставки бесконечного цикла в список.
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 listfor(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 мы создали цикл внутри связанного списка, результат становится истинным.
Результат работы вышеуказанной программы следующий:
Loop Existence : false [Line 15]Loop Existence : true [Line 16]
Как видите, как только мы вставляем цикл в строку № 16, наша реализация алгоритма способна его обнаружить.