English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية

Основной учебник Java

Java управление потоком

Java массив

Java面向对象(I)

Java面向对象(II)

Java面向对象(III)

Обработка исключений Java

Java список (List)

Java Queue (очередь)

Java Map集合

Java Set集合

Java Вход/Выход (I/O)

Java Reader/Writer

Другие темы Java

Java программа для проверки наличия цикла в LinkedList

Java полный список примеров

В этом примере мы изучим, как проверять наличие цикла в LinkedList на Java.

Чтобы понять этот пример, вам следует знать следующееJava программированиеТема:

Пример: Проверка наличия цикла в LinkedList

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 есть цикл, они встретятся.

Java полный список примеров