Java 程序：检测 LinkedList 中的循环

要理解这个示例，你需要了解以下 Java 编程主题：

Java LinkedList - Java 方法

示例：在 LinkedList 中检测循环

class LinkedList {

  // 创建 Node 类的对象
  // 代表链表的头部
  Node head;

  // 静态内部类
  static class Node {
    int value;

    // 将每个节点连接到下一个节点
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  // 检查是否存在循环
  public boolean checkLoop() {

    // 在链表开始处创建两个引用
    Node first = head;
    Node second = head;

    while(first != null && first.next !=null) {

      // 将 first 引用移动 2 个节点
      first = first.next.next;

      // 将 second 引用移动 1 个节点
      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("\nLinkedList 中存在循环。");
    }
    else {
      System.out.println("\nLinkedList 中不存在循环。");
    }
  }
}

输出

LinkedList: 1 2 3 4
LinkedList 中存在循环。

在上面的示例中，我们已经在 Java 中实现了一个 LinkedList。我们使用了 Floyd 判圈算法 来检查 LinkedList 中是否存在循环。

注意 checkLoop() 方法中的代码。这里，我们有两个名为 first 和 second 的变量，它们遍历 LinkedList 中的节点。

first - 单次迭代遍历 2 个节点
second - 单次迭代遍历 1 个节点

两个节点以不同的速度遍历。因此，如果 LinkedList 中存在循环，它们将会相遇。

Java 程序：检测 LinkedList 中的循环

示例：在 LinkedList 中检测循环​

示例：在 LinkedList 中检测循环