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 实例大全

在此示例中,我们将学习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() {

    //在LinkedList的开头创建两个引用
    Node first = head;
    Node second = head;

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

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

      //将第二个引用移动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("\n在 LinkedList 中有一个循环.");
    }
    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 实例大全