English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
В этом примере мы изучим, как проверять наличие цикла в LinkedList на Java.
Чтобы понять этот пример, вам следует знать следующееJava программированиеТема:
class LinkedList { //创建Node类的对象 //表示链表的头部 Node head; //静态内部类 static class Node { int value; // Каждая нода связана с последующей нодой Node next; Node(int d) { value = d; next = null; } } // Проверка наличия цикла public boolean checkLoop() { // В начале LinkedList создаются две ссылки Node first = head; Node second = head; while(first != null && first.next != null) { // Первая ссылка передвигается на два узла first = first.next.next; // Вторая ссылка передвигается на один узел second = second.next; // Если два ссылки равны (встречаются) if(first == second) { return true; } } return false; } public static void main(String[] args) { // Создается объект LinkedList LinkedList linkedList = new LinkedList(); // Каждому узлу списка присваивается значение linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); // Каждая нода списка связана с последующей нодой linkedList.head.next = second; second.next = third; third.next = fourth; // В LinkedList создается цикл fourth.next = second; // Вывод значения узла System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; i++; } // Проверка метода на наличие цикла boolean loop = linkedList.checkLoop(); if(loop) { System.out.println("\nВ LinkedList есть цикл."); } else { System.out.println("\nВ LinkedList нет цикла."); } } }
Результат вывода
LinkedList: 1 2 3 4 В LinkedList есть цикл.
В предыдущем примере мы использовали Java Реализовали LinkedList. Мы использовалиАлгоритм поиска цикла Floydчтобы проверить, существует ли цикл в LinkedList.
Внимание, код в методе checkLoop(). Здесь у нас есть две переменные first, second, они итерируют узлы LinkedList.
first - В одном итерации используется два узла для итерации
second - В одном итерации используется один узел для итерации.
Два узла с разной скоростью итерации. Таким образом, если в LinkedList есть цикл, они встретятся.