在此示例中,我们将学习Java中的检测LinkedList中是否存在循环。
要理解此示例,您应该了解以下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) { //将第一个引用移动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中有循环,它们将相遇。